F - 極小部分列

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

文字列 SQ 個のクエリが与えらます。

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 は小文字アルファベットのみからなる

入力

入力は以下の形式で標準入力から与えられる。

S
Q
T_1
T_2
:
T_Q

出力

i 番目のクエリの答えの文字列が Sl 文字目から r 文字目までの部分文字列であるとき、i 行目に l,r を空白区切りで出力せよ。ただし、ST_i を部分列として含まない場合は代わりに -1i 行目に出力せよ。


入力例 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 文字目までの部分文字列 abT_1 を部分列として含む極小な部分文字列ですが、axb の方が左にあるためこちらは答えとはなりません。

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