Decreasing String
Contest: Educational Codeforces Round 156 (Rated for Div. 2)
Difficulty rating: 1600
Tags: implementation, strings

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
cab
6
abcd
9
x
1

Example output:
abx

Editorial:
Let's analyze in which order the characters should be removed from the given string. Suppose we want to remove a character so that the resulting string is lexicographically smallest. We can show that the best option is to find the leftmost pair of adjacent characters $$$S_i, S_{i+1}$$$ such that $$$S_i > S_{i+1}$$$: removing $$$S_i$$$ will decrease the character on that position; if you remove some character to the right of $$$S_i$$$, the $$$i$$$-th character won't decrease; and if you remove some character to the left of $$$S_i$$$, you might accidentally increase some character before the $$$i$$$-th position (we chose the leftmost such pair, so the prefix until the $$$i$$$-th character is non-decreasing). If there is no such pair of adjacent characters, you should remove the last character of the string. Unfortunately, implementing it naively is too slow (the solution will work in $$$O(n^2)$$$). Thankfully, there is a way to determine in which all characters are removed in $$$O(n)$$$.
Maintain a stack of characters (initially empty) and iterate over the string from left to right. When you encounter a character, if the stack is empty or the character on top of the stack is not greater than the current one, you don't have to remove anything, just push the new character into the stack. But if the character on top of the stack is greater than the new one, then we have found a pair of adjacent characters which meets the condition; so, the character on top of the stack is the next to remove. Pop the topmost element of the stack. Note that we don't push the new character into the stack yet, because the next element on top of the stack might still be greater — in that case, this is the next character to remove (and we pop it), and so on. In the end, the character in the stack will be non-descending from the bottom of the stack to the top, and we should remove them from top to bottom. That's how we can find in which order characters are removed.
The rest is quite easy: locate in which of the strings $$$s_1, s_2, \dots, s_n$$$ the position $$$pos$$$ occurs, remove the required number of characters, and print the corresponding character of the resulting string.
Minor detail which can make the implementation easier: if you append some character which is less than a to the end of the given string, you don't have to consider the case when there's no pair of adjacent characters $$$S_i > S_{i+1}$$$.