Một xâu ký tự được gọi là xâu ký tự hằng nếu mọi ký tự của xâu đều
giống nhau. Ví dụ, p
, vv
hay hhh
là các xâu ký tự hằng, còn
gspvhcute
thì không.
Một xâu con liên tiếp của xâu ký tự ~s = s_1 s_2 \ldots s_n~ là xâu ký
tự có dạng ~s_l s_{l+1} \ldots s_{r-1} s_r~ với
~1 \leq l \leq r \leq n~. Ví dụ, xâu ppvhhh
có ~21~ xâu con liên tiếp,
trong đó có ~10~ xâu ký tự hằng: h
xuất hiện ~3~ lần, p
và hh
xuất
hiện ~2~ lần, mỗi xâu pp
, v
và hhh
xuất hiện ~1~ lần.
Cho hai số nguyên ~n~ và ~k~, xét tập hợp ~\Omega~ gồm các xâu ký tự ~s~ chỉ gồm chữ cái in thường có chính xác ~n~ xâu con liên tiếp là xâu ký tự hằng. Hãy sắp xếp các xâu ký tự trong ~\Omega~ theo thứ tự từ điển, và in ra xâu ký tự thứ ~k~ trong tập hợp này.
Input
File input gồm ~3~ câu hỏi, mỗi câu hỏi được thể hiện bởi hai số ~n~ và ~k~ được viết trên một dòng với ~1 \leq n \leq 10^7~ và ~1 \leq k \leq 3 \cdot 10^{18}~. Dữ liệu vào đảm bảo số ~k~ không lớn hơn lực lượng của tập hợp ~\Omega~ được định nghĩa ở trên.
Output
Với mỗi câu hỏi, in ra xâu ký tự cần tìm trên một dòng.
Giới hạn
- Subtask ~1~ (~10~ điểm): ~n \leq 2~
- Subtask ~2~ (~14~ điểm): ~n \leq 4~
- Subtask ~3~ (~20~ điểm): ~n \leq 15~ và ~k \leq 10^6~
- Subtask ~4~ (~16~ điểm): ~k = 1~
- Subtask ~5~ (~20~ điểm): ~n \leq 100~
- Subtask ~6~ (~20~ điểm): Không có ràng buộc gì thêm
Sample Input 1
1 1
1 2
1 3
Sample Output 1
a
b
c
Sample Input 2
3 1
3 2
3 3
Sample Output 2
aa
aba
abc
Sample Input 3
2 168
3 9899
4 43749
Sample Output 3
gs
pvh
cute
Sample Input 4
22 7
19 97
56 23
Sample Output 4
aaaaaah
aaaaabaev
aaaaaaaaaax
Bình luận