JB 热爱字符串问题。这是 JB 创造的另一个有趣的字符串问题。

假设有一个字符串 $S$，JB 会列出 $S$ 的所有子串。对于一个子串 $x$，如果它在 $S$ 中出现多次，JB 会将其列出多次。之后，JB 会将列表中的字符串按字典序排序；如果两个字符串相同，则按它们在 $S$ 中出现的位置进行排序。在对字符串排序后，JB 会按顺序将这些字符串连接成一个字符串 $T$。

现在 JB 会向你提出 $Q$ 个询问，每个询问由一个整数 $k$ 表示。JB 希望你告诉他，字符串 $T$ 中第 $k$ 个字符在 $S$ 中的位置是什么？

输入格式

第一行包含一个字符串 $S(1 \le |S| \le 5 \times 10^5)$，仅包含小写字母。 第二行包含一个整数 $Q(1 \le Q \le 5 \times 10^5)$。 接下来的 $Q$ 行，每行包含一个整数 $k(1 \le k \le |T|)$。

输出格式

对于每个询问，输出一个整数表示答案。

样例

样例输入 1

pbpbppb
3
1
2
3

样例输出 1

2
4
7

样例输入 2

potatop
3
6
30
60

样例输出 2

6
3
4