← 返回题目列表

Codeforces · 1328/B

B. 第K个美丽的字符串

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

对于给定的整数 $$$n$$$ ($$$n > 2$$$) 让我们写下所有长度为 $$$n$$$ 的字符串,其中包含 $$$n-2$$$ 按字典顺序(字母顺序)字母 'a' 和两个字母 'b'。

回想一下,如果存在这样的 $$$i$$$ ($$$1 \le i \le n$$$),则 $$$s_i < t_i$$$,并且对于任何 $$$j$$$ ($$$1 \le j < i$$$) $$$s_j = t_j$$$。现代编程语言中字符串的字典比较是通过运算符<来实现的。

例如,如果 $$$n=5$$$ 字符串是(顺序很重要):

1. aaabb
2. aabab
3.阿巴
4.阿巴布
5.贝巴
6.阿巴
7. 咩咩
8.粑粑
9.粑粑
10.bbaaa

很容易证明这样的字符串列表将恰好包含 $$$\frac{n \cdot (n-1)}{2}$$$ 字符串。

您将获得 $$$n$$$ ($$$n > 2$$$) 和 $$$k$$$ ($$$1 \le k \le \frac{n \cdot (n-1)}{2}$$$)。打印列表中第 $$$k$$$ 个字符串。

输入

输入包含一个或多个测试用例。

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例都写在包含两个整数 $$$n$$$ 和 $$$k$$$ 的单独行上 ($$$3 \le n \le 10^5, 1 \le k \le \min(2\cdot10^9, \frac{n \cdot (n-1)}{2})$$$。

测试中所有测试用例的值 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,从上述所有长度为 $$$n$$$ 的字符串列表中打印第 $$$k$$$ 个字符串。列表中的字符串按字典顺序(字母顺序)排序。

示例

输入 #1

7
5 1
5 2
5 8
5 10
3 1
3 2
20 100

输出 #1

aaabb
aabab
baaba
bbaaa
abb
bab
aaaaabaaaaabaaaaaaaa