시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB129872.727%

문제

Consider all binary strings that have exactly $n$ different non-empty subsequences (different by contents). Sort the strings in lexicographic order. Find the $k$-th such string in this order.

입력

Each test contains multiple test cases. The first line contains an integer $t$ ($1\le t \le 100$) --- the number of test cases. The descriptions of the $t$ test cases follow.

The description of each test case consists of a single line with two integers $n$ and $k$ ($1 \le n, k \le 10^9$).

출력

For each test case, if there are less than $k$ binary strings with exactly $n$ different non-empty subsequences, print -1 on a single line. Otherwise, print lexicographically $k$-th of them on the next two lines in the following format:

A non-empty binary string can be uniquely described by its first character and list of sizes of blocks of equal characters. You should print $m$ and $c$ on the first line, where $m$ is the number of blocks and $c$ is the first character. Then, on the second line, print the sizes of blocks $L_1, L_2, \ldots, L_m$ in order.

예제 입력 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

노트

The actual strings corresponding to answers to the sample are:

000
01
10
111
-1
000...000 (1000000000 times)
0000000001100100000011011000000010
00000000011111111100000000110000111100011111000