Decreasing String
题意翻译
有 $t$ 组测试点,每组测试点给出字符串 $s_1$ 和 一个整数 $pos$。
以下列规则得到字符串 $ S $ :
- 从 $ s_{i - 1} $ 中删除一个字符,字典序最小的记为 $ s_i $
- $S = s_1 + s_2 + \dots + s_n $
输出字符串 $ S $ 第 $pos$ 个位置上的字符(即 $ S_{pos} $)。
题目描述
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} $ ).
输入输出格式
输入格式
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 $ .
输出格式
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.
输入输出样例
输入样例 #1
3
cab
6
abcd
9
x
1
输出样例 #1
abx