問題文

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

入力

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

$S$ $Q$ $T_1$ $T_2$ $:$ $T_Q$

出力

$i$ 番目のクエリの答えの文字列が $S$ の $l$ 文字目から $r$ 文字目までの部分文字列であるとき、$i$ 行目に $l,r$ を空白区切りで出力せよ。ただし、$S$ が $T_i$ を部分列として含まない場合は代わりに -1 を $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$ を部分列として含むような部分文字列を含むためです。