An Array and Addition Again#228

An Array and Addition Again

1 second

256 megabytes

Hard

Given an array $a$ with elements numbered from $1$ to $100$ . Initially, $a_{i} = 0$ a_i = 0 for $1 \leq i < 100$ 1 \leq i < 100, and the last element $a_{100}$ 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}$ p_1, p_2, \dots, p_m ( $1 \leq p_{i} < 100$ 1\le p_i < 100) and sequentially execute assignments $a_{p_{i}} \leftarrow (a_{p_{i}} + a_{p_{i} + 1})$ 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 \leq t \leq 100$ 1 \le t \le 100, $0 \leq g \leq 5$ 0 \leq g \leq 5) — the number of input sets and the test block number, respectively.

In the next $t$ lines, there is a single integer $n$ ( $1 \leq n \leq 1 0^{18}$ 1 \le n \le 10^{18}) — the value that $a_{1}$ 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 \leq m \leq 2000$ 0 \leq m \leq 2000) in the first line — the number of increase operations.

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

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

Examples

Example

1 0
1

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

Example

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$ n = 16. The first 8 elements of the array $a$ after performing the next operation look as follows:

$p_{1}$ p_1 = 99, $a = [0, 0, 0, 0, 0, 0, 0, 0, \dots, 0, 0, 1, 1]$ a = [0, 0, 0, 0, 0, 0, 0, 0, \ldots, 0, 0, 1, 1];
$p_{2}$ p_2 = 98, $a = [0, 0, 0, 0, 0, 0, 0, 0, \dots, 0, 1, 1, 1]$ a = [0, 0, 0, 0, 0, 0, 0, 0, \ldots, 0, 1, 1, 1];
$\dots$
$p_{93} = 7$ p_{93} = 7, $a = [0, 0, 0, 0, 0, 0, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 0, 0, 0, 0, 1, 1, \ldots, 1, 1, 1, 1];
$p_{94} = 6$ p_{94} = 6, $a = [0, 0, 0, 0, 0, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 0, 0, 0, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{95} = 5$ p_{95} = 5, $a = [0, 0, 0, 0, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 0, 0, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{96} = 4$ p_{96} = 4, $a = [0, 0, 0, 1, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 0, 1, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{97} = 4$ p_{97} = 4, $a = [0, 0, 0, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 0, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{98} = 3$ p_{98} = 3, $a = [0, 0, 2, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 2, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{99} = 3$ p_{99} = 3, $a = [0, 0, 4, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 0, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{100} = 2$ p_{100} = 2, $a = [0, 4, 4, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 4, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{101} = 2$ p_{101} = 2, $a = [0, 8, 4, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [0, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{102} = 1$ p_{102} = 1, $a = [8, 8, 4, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [8, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1];
$p_{103} = 1$ p_{103} = 1, $a = [16, 8, 4, 2, 1, 1, 1, 1, \dots, 1, 1, 1, 1]$ a = [16, 8, 4, 2, 1, 1, 1, 1, \ldots, 1, 1, 1, 1].

Scoring

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

( $4$ points): $n \leq 100$ n \leq 100;
( $6$ points): $n = k^{2}$ n = k^2 for some integer $1 \leq k \leq 100$ 1 \le k \le 100;
( $10$ points): $n = (2^{k} - 1)$ n = (2^k - 1) for some integer $k$ ;
( $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$ 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots);
(up to $67$ points): without additional restrictions. Let the maximum number of increment operations used be $c$ . If $c \leq 300$ c \le 300, you will receive $67$ points, otherwise you will receive ( $17 + ⌊ \frac{2000 - c}{34} ⌋$ 17 + \left \lfloor \frac{2000 - c}{34} \right \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))