AT_s8pc_5_h Percepts of Atcoder

E869120 决定从今年开始到接下来 $Q$ 年，每年将一个字符串送给 square1001。他从字符串 $S$ 中选择赠送的字符串，并遵循以下规则： * 将字符串 $S$ 的所有子串的集合记为 $T$。这里，$S$ 的子串是指从 $S$ 中移除任意数量的字符（包括不移除）后形成的至少包含一个字符的字符串。 * 将集合 $T$ 按字典顺序排序后，应赠送第 $K$ 个字符串。 例如，如果 E869120 最喜欢的字符串是 `aqua`，则 $T$ 将是 `['a', 'aa', 'aq', 'aqa', 'aqu', 'aqua', 'au', 'aua', 'q', 'qa', 'qu', 'qua', 'u', 'ua']`。当 $K=10$ 时，应赠送按字典序排序的第 $10$ 个字符串 `qa`。 然而，$K$ 的值会每年变化。因此，对于第 $i$ 年，给定 $K_i$ 为第 $i$ 年的 $K$ 值，需要找出每年应赠送的字符串的最后 $p_i$ 个字符。

首先输入字符串 $S$。 接着输入一个整数 $Q$，表示接下来的年数。 随后输入 $Q$ 行，每行包含两个整数 $K_i$ 和 $p_i$，分别表示第 $i$ 年的 $K$ 值和应输出的字符数。

输出 $Q$ 行。第 $i$ 行应输出第 $i$ 年应赠送的字符串的最后 $p_i$ 个字符。 **如果不存在应赠送的字符串，输出 -1。若应赠送的字符串长度小于 $p_i$，则直接输出该字符串。例如，如果应赠送的字符串是 "abcde" 且 $p_i=7$，则输出 "abcde"。**

* $1 \leq Q \leq 10^5$，保证字符串 $S$ 由小写字母组成，且 $|S| \leq {3\times 10^5}$。 * $p_i$ 是 $|S|$ 以内的正整数，满足 $p_1 + p_2 + ... + p_Q \leq 10^6$。 * $K_i$ 是 $10^{18}$ 以内的正整数。 * $|S|$ 表示 $S$ 的字符串位数。