JB 是后缀自动机领域的国家奥赛导师。今天他提出了以下问题。

假设你有一个字符串 $S$，我们写下 $S$ 中所有不同的子串。然后我们将这些字符串按长度递增的顺序排序。对于长度相同的字符串，字典序较小的排在前面。现在我们得到了一个有序的字符串序列 $A$。

JB 有 $Q$ 个询问，对于每个询问，他会给你一个整数 $k$，你需要告诉他序列 $A$ 中的第 $k$ 个字符串。

为了简化问题，你只需要告诉他该字符串在 $S$ 中第一次出现时的左端点和右端点位置。

输入格式

第一行包含一个字符串 $S$ ($1 \le |S| \le 10^6$)，仅包含小写字母。 第二行包含一个整数 $Q$ ($1 \le Q \le 10^6$)。 接下来的 $Q$ 行描述询问，每行包含一个整数 $k$ ($1 \le k \le 10^{12}$)。

输出格式

对于每个询问，输出两个整数 $l, r$，表示答案字符串在 $S$ 中第一次出现时的左端点和右端点位置。如果 $k$ 大于序列 $A$ 的长度，则输出“-1 -1”。

样例

样例输入 1

ccpcguilin
5
1
10
4
8
26

样例输出 1

1 1
2 3
8 8
1 2
4 7

样例输入 2

banana
3
5
10
16

样例输出 2

1 2
2 5
-1 -1