← 返回题目列表

Codeforces · 1886/C

C. 减少字符串

中文机器翻译题面 查看原题

回想一下,如果 $$$a$$$ 是 $$$b$$$ 的前缀(并且 $$$a \ne b$$$),或者存在索引 $$$i$$$ ($$$1 \le i \le \min(|a|, |b|)$$$),使得 $$$a_i < b_i$$$,并且对于任何索引 $$$j$$$ ($$$1 \le j < i$$$) $$$a_j = b_j$$$。

考虑一系列字符串 $$$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}$$$)。

输入

第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,打印答案 - 字符串 $$$S$$$ 中位于 $$$pos$$$ 位置的字符。请注意,不同测试用例之间的答案不以空格或换行符分隔。

示例

输入 #1

3
cab
6
abcd
9
x
1

输出 #1

abx