4 字符串 (string)

4.1 问题描述

从分子水平研究生物大分子的结构与功能从而揭示生命现象的本质。 F现在要为你，F创造的生命，谱写人生。 F说，人生首先要有基调。于是有了一个字符串 $S$ 作为你人生的基调。 F说，人生要长，要复杂，于是将 $S$ 的所有子串按字典序排列后拼接起来得到了一个字符串 $T$ ，作为你的人生。相同的子串若出现多次，会被重复计入，出现位置靠前的在前。 于是你诞生了。因为你是个 OIer，你想询问 $Q$ 次： 如果你的人生的基调是 $S$，那么你人生的第 $x$ 个单位，即 $T$ 的第 $x$ 个字符是由基调 $S$ 中的哪个位置的字符构成的呢？

4.2 输入格式

第一行，一个仅包含小写英文字符的字符串 $S$。 第二行，一个整数 $Q$。 接下来 $Q$ 行，每行一个整数表示询问的 $x$。

4.3 输出格式

$Q$ 行，每行一个正整数，表示答案。

4.4 样例 1 输入

pbpbppb
3
1
2
3

4.5 样例 1 输出

2
4
7

大样例

4.6 数据规模与约定

$1 ≤ Q, n ≤ 10^5$。 保证 $x$ 合法。本题共有 20 个测试点，每个测试点均有 5 分。表格内的 $T$ 表示数据点编号。对于编号为奇数的测试点，满足字符集为 ${a,b}$。