310777: CF1886C. Decreasing String

C. Decreasing Stringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 < b_i$, and for any index $j$ ($1 \le j < 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}$).

Input

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$.

Output

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.

ExampleInput

3
cab
6
abcd
9
x
1

Output

abx

题目大意：
这个题目是关于一个字符串序列的问题。给定一个字符串s1，其余的字符串si（i>1）是根据前一个字符串si-1删除一个字符后得到的，删除的方式是使得新的字符串在字典序上尽可能小。然后，我们得到一个由所有这些字符串连接而成的字符串S。题目要求输出字符串S中第pos个位置的字符。

输入数据格式：
第一行包含一个整数t，表示测试用例的数量（1≤t≤10^4）。
每个测试用例包含两行：
第一行是一个字符串s1（1≤|s1|≤10^6），只包含小写拉丁字母。
第二行是一个整数pos（1≤pos≤|s1|×(|s1|+1)/2），表示要查询的字符在字符串S中的位置。
所有测试用例的s1长度之和不超过10^6。

输出数据格式：
对于每个测试用例，输出字符串S中第pos个位置的字符。不同测试用例之间的答案不需要用空格或换行符分隔。

示例：
输入：
3
cab
6
abcd
9
x
1

输出：
abx

请注意，题目中的公式是用LaTeX格式编写的，这里无法直接显示LaTeX格式的公式，但是可以在支持LaTeX的编辑器或者网站中查看。题目大意： 这个题目是关于一个字符串序列的问题。给定一个字符串s1，其余的字符串si（i>1）是根据前一个字符串si-1删除一个字符后得到的，删除的方式是使得新的字符串在字典序上尽可能小。然后，我们得到一个由所有这些字符串连接而成的字符串S。题目要求输出字符串S中第pos个位置的字符。 输入数据格式： 第一行包含一个整数t，表示测试用例的数量（1≤t≤10^4）。 每个测试用例包含两行： 第一行是一个字符串s1（1≤|s1|≤10^6），只包含小写拉丁字母。 第二行是一个整数pos（1≤pos≤|s1|×(|s1|+1)/2），表示要查询的字符在字符串S中的位置。 所有测试用例的s1长度之和不超过10^6。 输出数据格式： 对于每个测试用例，输出字符串S中第pos个位置的字符。不同测试用例之间的答案不需要用空格或换行符分隔。 示例： 输入： 3 cab 6 abcd 9 x 1 输出： abx 请注意，题目中的公式是用LaTeX格式编写的，这里无法直接显示LaTeX格式的公式，但是可以在支持LaTeX的编辑器或者网站中查看。