#P18652. Exact Subsequences

Exact Subsequences

Exact Subsequences

考虑所有恰好具有 nn 个不同非空子序列的二进制字符串。这里不同按子序列的内容区分,同一内容从不同位置选取得到时只计一次。将这些字符串按字典序从小到大排序,请求出第 kk 个字符串。

子序列指从字符串中删除若干字符(也可以不删除),保持其余字符的相对顺序后得到的字符串。字典序按 0<10<1 比较;若一个字符串是另一个的真前缀,则较短者在前。

输入格式

第一行一个整数 tt(1≤t≤1001\le t\le100),表示测试用例数。

每个测试用例占一行,包含两个整数 n,kn,k(1≤n,k≤1091\le n,k\le10^9)。

输出格式

对每个测试用例,如果满足要求的二进制字符串不足 kk 个,输出一行 -1。

否则,输出字典序第 kk 个字符串的游程编码,占两行:

第一行输出 mm 和 cc,其中 mm 是极大连续相同字符段的数量,cc 是第一段的字符(0 或 1)。

第二行依次输出这 mm 段的长度 L1,L2,…,LmL_1,L_2,\ldots,L_m。各长度均为正整数,相邻段的字符交替变化。例如 000110 的表示为第一行“3 0”、第二行“3 2 1”。每个非空二进制串的这种表示唯一。

样例输入 1

8
3 1
3 2
3 3
3 4
3 5
1000000000 1
99824 4353
2129721 207087

样例输出 1

1 0
3
2 0
1 1
2 1
1 1
1 1
3
-1
1 0
1000000000
11 0
9 2 2 1 6 2 1 2 7 1 1
9 0
9 9 8 2 4 4 3 5 3

样例说明

八个测试用例对应的实际字符串依次为:

000
01
10
111
-1
000...000(共 1000000000 个 0)
0000000001100100000011011000000010
00000000011111111100000000110000111100011111000

第六行的省略写法仅用于说明;程序必须输出样例输出中的游程编码,不能输出省略号。第五个用例不存在答案。