C - 子序列

题目描述

给定 $n,k$ 。定义一个字符串是合法的，当且仅当其本质不同的非空子序列数量为 $n$ 。

找到字典序第 $k$ 小的非空且合法的字符串，满足字符集在 $\{0,1\}$ 内。若无解输出 $-1$ 。

输入格式

本题包含多组数据。第一行输入一个整数 $T$ ，代表数据组数。

每组数据包含一行两个整数 $n,k$ 。

输出格式

若无解输出 $-1$ ，否则输出这个串。

由于串的长度可能非常大，我们按以下方式输出这个串：

不妨设这个串的字符依次是 $s_1,s_2,\dots,s_m$ 。令 $n=\sum\limits_{1\le i<m} [s_i\neq s_{i+1}]+1$ 。

令 $a_k$ 为第 $k$ 小的满足 $s_i\neq s_{i+1}$ 的位置，特别的，$a_n=m,a_0=0$ 。

则第一行输出两个整数 $n,s_1$ 。

第二行输出 $n$ 个整数，其中第 $k$ 个整数表示 $a_k-a_{k-1}$ 。

构造的数据保证输出的串满足 $n\le 1145$ 。

样例

样例输入

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

样例输出

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

数据范围

对于所有数据，$T\le 100;n,k\le 10^9$ 。

子任务 1 ( 20% ) : $T=1,1\le n\le 10$ 。

子任务 2 ( 20% ) : $T=1,1\le n\le 1000$ 。

子任务 3 ( 30% ) : $T=1,1\le n\le 10^6$ 。

子任务 4 ( 30% ) : 无特殊限制。