An Array and Addition Again

Given an array $a$ with elements numbered from $1$ to $100$. Initially, $a_i=0$ for $1\le i<100$, and the last element $a_{100}$ is equal to $1$.

The array $a$ can be modified using increment operations. To perform $m$ increment operations, it is necessary to select $m$ integers $p_1,p_2,\dots ,p_m$ ($1\le p_i<100$) and sequentially execute assignments $a_{p_i}\leftarrow (a_{p_i}+a_{p_i+1})$ for $i$ from $1$ to $m$.

Given an integer $n$, find the sequence of increment operations after which the element at the first position in array $a$ becomes equal to $n$.

Input

The first line contains two integers $t$ and $g$ ($1\le t\le 100$, $0\le g\le 5$) — the number of input sets and the test block number, respectively.

In the next $t$ lines, there is a single integer $n$ ($1\le n\le 10^{18}$) — the value that $a_1$ should be equal to after performing the increment operations in the corresponding set.

Output

For each set of input data, output one integer $m$ ($0\le m\le 2000$) in the first line — the number of increase operations.

In the second line, output $m$ integers $p_i$ ($1\le p_i<100$) — the parameters of the increase operations.

If there are multiple correct answers, you can output any of them.

Examples

1 0
1

99
99 98 ... 7 6 5 4 3 2 1

2 0
3
16

101
99 98 ... 7 6 5 4 3 2 1 1 1
103
99 98 ... 7 6 5 4 4 3 3 2 2 1 1

Note

For clarity, the examples of the input data in the problem statement have been reduced. To obtain the correct answer, replace "..." with the sequence of integers from $97$ to $8$.

Let's consider the second set of input data for the second example, where $n=16$. The first 8 elements of the array $a$ after performing the next operation look as follows:

• $p_1$ = 99, $a=[0,0,0,0,0,0,0,0,\dots ,0,0,1,1]$;

• $p_2$ = 98, $a=[0,0,0,0,0,0,0,0,\dots ,0,1,1,1]$;

• $\dots$

• $p_{93}=7$, $a=[0,0,0,0,0,0,1,1,\dots ,1,1,1,1]$;

• $p_{94}=6$, $a=[0,0,0,0,0,1,1,1,\dots ,1,1,1,1]$;

• $p_{95}=5$, $a=[0,0,0,0,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{96}=4$, $a=[0,0,0,1,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{97}=4$, $a=[0,0,0,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{98}=3$, $a=[0,0,2,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{99}=3$, $a=[0,0,4,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{100}=2$, $a=[0,4,4,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{101}=2$, $a=[0,8,4,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{102}=1$, $a=[8,8,4,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{103}=1$, $a=[16,8,4,2,1,1,1,1,\dots ,1,1,1,1]$.

Scoring

The first four test blocks allow using no more than 300 increment operations.

1. ($4$ points): $n\le 100$;

2. ($6$ points): $n=k^2$ for some integer $1\le k\le 100$;

3. ($10$ points): $n=(2^k-1)$ for some integer $k$;

4. ($13$ points): $n$ is a Fibonacci number (i.e., $n$ is an element of the sequence where each element is the sum of the two previous ones: $1,1,2,3,5,8,13,21,34,\dots$);

5. (up to $67$ points): without additional restrictions. Let the maximum number of increment operations used be $c$. If $c\le 300$, you will receive $67$ points, otherwise you will receive ($17+\lfloor \frac{2000-c}{34}\rfloor$) points.

The C++ code that calculates the number of points for the last test block depending on the number of increment operations used is:

((c <= 300) ? 67 : (17 + (2000 - c) / 34))