E. 生命线 / MST & LCP

时间限制： 2.0 秒 空间限制： 512 MiB

题目描述

对于一个长为 n 的、仅由 a,b,...,z 构成的字符串 s，考虑一张含 n 个点的无向带 权图，每两个点 i, j (i ̸= j) 间有权值为 LCP(sufi, sufj)† 的边，其中 sufi = s[i : n]。 Ecrade_ 定义字符串 s 的价值为该图 最大生成树的边权之和。 Ecrade_ 想要请你找出所有长为 n 的、仅由 a,b,...,z 构成的字符串中，价值第 k 小的任意一个。 † LCP(s1, s2) 定义为字符串 s1 与 s2 的最长公共前缀的长度。

输入格式

从标准输入读入数据。 第一行一个整数 T (1 ≤ T ≤ 2 × 10^5)，表示测试数据组数。 对于每组测试数据， 一行两个整数n, k (1 ≤ n, ∑ n ≤ 4 × 10^5, 1 ≤ k ≤ min(26^n, 10^15))。

输出格式

输出到标准输出。 对于每组测试数据， 第一行输出第k 小的价值， 第二行输出一行一个长为n 的、 价 值第 k 小的字符串。若有多个字符串满足条件，输出其中任意一个即可。

样例

样例 1 输入

3
2 1
2 676
3 16000

样例 1 输出

0
ab
1
aa
1
aab

样例 1 解释

• 对于第一组测试数据，长为 2 的字符串中，第 1 小（即最小）的价值为 0，一个 满足条件的字符串为 hi。当然，ab、yz 等字符串也满足条件。
• 对于第二组测试数据，长为 2 的字符串中，第 676 小（即最大）的价值为 1，一 个满足条件的字符串为 gg。当然，aa、zz 等字符串也满足条件。
• 对于第三组测试数据，长为 3 的字符串中，第 16000 小的价值为 1，一个满足条 件的字符串为 qwq。当然，cpp、lol 等字符串也满足条件。