問題文

大学 A と大学 B は統合することになりました。大学 A の大学名は A 、大学 B の大学名は B です。統合後の新しい大学名 C を考えましょう。具体的には、以下のようにして C を定めます。

• A の空でない部分列を 1 つとって a とする。
• B の空でない部分列を 1 つとって b とする。
• C を a と b をこの順で連結した文字列とする。

Q 個の文字列 S_1, S_2, \dots, S_Q が与えられます。それぞれの文字列が C としてあり得るかどうか判定し、あり得る場合は、|\text{len}(a) - \text{len}(b)| としてあり得る最小値を求めてください。( \text{len}(x) は x の長さを表す)

制約

• Q は整数である。
• 1 ≤ Q ≤ 10^6
• A, B, S_1, S_2, \dots, S_Q は英小文字・英大文字・空白からなる文字列である。
• 1 ≤ \text{len}(A), \text{len}(B) ≤ 10^5
• 2 ≤ \text{len}(S_i) ≤ 10^5 (1 ≤ i ≤ Q)
• \displaystyle\left(\sum_{i = 1}^Q\text{len}(S_i)\right) ≤ 2 \times 10^6

部分点

• Q ≤ 20 を満たすデータセットに正解すると 100 点が与えられる。

入力例 1

Tokyo Institute of Technology
Tokyo Medical and Dental University
10
The University
Tokyo University
kyoto University
Tokyo Tech
TMDU
Kyoto University
The University of Tokyo
Tokyo Technology and Medical and Dental University
   Tehnoooorsty
Tokyo

出力例 1

10
4
4
-1
2
-1
-1
-1
3
1

• S_1 = {}The University について、a = {}Th 、b = {}e University とすると、C = {}The University とできます。このとき、|\text{len}(a) - \text{len}(b)| = 10 となります。
• S_4 = {}Tokyo Tech について、b は空であってはいけないことに注意してください。
• 一般的な問題と異なり、空白も文字列の一部であることに注意してください。