问题

给定字符串 $S$ 和 $Q$ 个查询。

对于第 $i$ 个查询，给定字符串 $T_i$，请找出包含 $T_i$ 作为子序列的 $S$ 的最左边的最小子串。

这里字符串 $s$ 是最小的意思是，$s$ 是包含 $T_i$ 作为子序列的所有子串中最短的。

约束条件

• $1≤|S|≤10^5$
• $1≤Q≤10^5$
• $1≤|T_i|$
• $|T_i|$ 的总和不超过 $10^5$
• $S, T_i$ 只包含小写字母

输入

输入从标准输入中给出，具体格式如下：

$S$

$Q$

$T_1$

$T_2$

$\cdots$

$T_Q$

输出

如果第 $i$ 个查询的答案是 $S$ 的子串从第 $l$ 个字符到第 $r$ 个字符组成，将 $l$ 和 $r$ 在第 $i$ 行以空格分隔输出。如果 $S$ 不包含 $T_i$ 作为子序列，则在第 $i$ 行输出 -1。

输入示例 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

以下为对第一个查询的解释：

答案是子串 axb，从第二个字符到第四个字符。

另外，子串 ab 也是包含 $T_1$ 作为子序列的最小子串，但是 axb 在左边，因此不是答案。

另外，aaxb 不是最小子串。因为它包含一个子串 axb，它是包含 $T_1$ 作为子序列的子串。