問題文

文字列 S と Q 個のクエリが与えらます。

i 番目のクエリでは文字列 T_i が与えられるので、T_i を部分列として含むような S の極小な部分文字列のうち最も左にあるものを求めてください。

ただし文字列 s が極小であるとは、s の部分文字列であって T_i を部分列として含むような s より短いものが存在しないことを指すものとします。

制約

• 1≦|S|≦10^5
• 1≦Q≦10^5
• 1≦|T_i|
• |T_i| の和は 10^5 を越えない
• S, T_i は小文字アルファベットのみからなる

入力例 1

aaxbab
12
ab
da
subsequence
aaxbab
a
aa
aaa
aaaa
ba
x
xb
xb

出力例 1

2 4
-1
-1
1 6
1 1
1 2
1 5
-1
4 5
3 3
3 4
3 4

1 番目のクエリについて説明します。

答えは 2 文字目から 4 文字目までの部分文字列 axb となります。

他にも　5 文字目から 6 文字目までの部分文字列 ab も T_1 を部分列として含む極小な部分文字列ですが、axb の方が左にあるためこちらは答えとはなりません。

また、aaxb は極小ではありません。 なぜなら axb という T_i を部分列として含むような部分文字列を含むためです。