CF1886C.Decreasing String

Recall that string $a$ is lexicographically smaller than string $b$ if $a$ is a prefix of $b$ (and $a \ne b$), or there exists an index $i$ ($1 \le i \le \min(|a|, |b|)$) such that $a_i \lt b_i$, and for any index $j$ ($1 \le j \lt i$) $a_j = b_j$.

Consider a sequence of strings $s_1, s_2, \dots, s_n$, each consisting of lowercase Latin letters. String $s_1$ is given explicitly, and all other strings are generated according to the following rule: to obtain the string $s_i$, a character is removed from string $s_{i-1}$ in such a way that string $s_i$ is lexicographically minimal.

For example, if $s_1 = \mathrm{dacb}$, then string $s_2 = \mathrm{acb}$, string $s_3 = \mathrm{ab}$, string $s_4 = \mathrm{a}$.

After that, we obtain the string $S = s_1 + s_2 + \dots + s_n$ ($S$ is the concatenation of all strings $s_1, s_2, \dots, s_n$).

You need to output the character in position $pos$ of the string $S$ (i. e. the character $S_{pos}$).

回忆一下，若字符串 $a$ 是字符串 $b$ 的前缀（且 $a \ne b$），或存在某个下标 $i$（满足 $1 \le i \le \min(|a|, |b|)$），使得 $a_i \lt b_i$，且对任意下标 $j$（满足 $1 \le j \lt i$）都有 $a_j = b_j$，则称字符串 $a$ 在字典序上小于字符串 $b$。

考虑一个由小写拉丁字母组成的字符串序列 $s_1, s_2, \dots, s_n$。其中字符串 $s_1$ 被显式给出，其余所有字符串均按如下规则生成：为得到字符串 $s_i$，需从字符串 $s_{i-1}$ 中删去一个字符，使得 $s_i$ 的字典序最小。

例如，若 $s_1 = \mathrm{dacb}$，则 $s_2 = \mathrm{acb}$，$s_3 = \mathrm{ab}$，$s_4 = \mathrm{a}$。

随后，我们构造字符串 $S = s_1 + s_2 + \dots + s_n$（即 $S$ 是所有字符串 $s_1, s_2, \dots, s_n$ 的拼接）。

你需要输出字符串 $S$ 中位置为 $pos$ 的字符（即字符 $S_{pos}$）。

The first line contains one integer $t$ — the number of test cases ($1 \le t \le 10^4$).

Each test case consists of two lines. The first line contains the string $s_1$ ($1 \le |s_1| \le 10^6$), consisting of lowercase Latin letters. The second line contains the integer $pos$ ($1 \le pos \le \frac{|s_1| \cdot (|s_1| +1)}{2}$). You may assume that $n$ is equal to the length of the given string ($n = |s_1|$).

Additional constraint on the input: the sum of $|s_1|$ over all test cases does not exceed $10^6$.

第一行包含一个整数 $t$ —— 测试用例的数量（$1 \le t \le 10^4$）。

每个测试用例由两行组成。第一行包含字符串 $s_1$（$1 \le |s_1| \le 10^6$），该字符串仅由小写拉丁字母组成；第二行包含整数 $pos$（$1 \le pos \le \frac{|s_1| \cdot (|s_1| +1)}{2}$）。你可以假设 $n$ 等于给定字符串的长度（即 $n = |s_1|$）。

输入的额外约束：所有测试用例中 $|s_1|$ 的总和不超过 $10^6$。

For each test case, print the answer — the character that is at position $pos$ in string $S$. Note that the answers between different test cases are not separated by spaces or line breaks.

对于每个测试用例，输出答案——即字符串 $S$ 中位置为 $pos$ 的字符。注意：不同测试用例的答案之间不以空格或换行符分隔。