题目描述

牛妹在无穷多个平行宇宙中跳跃，每个宇宙都有一个整数编号，且对于每个整数 $n\in \mathbf{Z}$，都有唯一一个宇宙的编号是 $n$。

牛妹掌握了三种空间跳跃技术，分别是：

1. 如果当前在编号为 $n$ 的宇宙，且 $\min(|n|,|n-d|)\le l$，则她可以跳跃到编号为 $n − d$ 的宇宙，其中 $d$ 和 $l$ 都是给定的正整数。
2. 如果当前在编号为 $n$ 的宇宙，则她可以跳跃到编号为 $2\times n$ 的宇宙。
3. 如果当前在编号为 $n$ 的宇宙，且 $n\equiv1\pmod3$，即 $n =\ldots , −5, −2,1,4, \ldots$ 时，她可以跳跃到编号为 $\frac{n-1}{3}$ 的宇宙。

牛妹一开始在编号为 $1$ 的宇宙中，她可以随意的使用这三种空间跳跃技术在宇宙中跳跃。她有 $q$ 个想去的目的地 $n_1, n_2, \ldots , n_q$，她想知道对于每个 $i$，她需要怎么从编号为 $1$ 的宇宙跳跃到编号为 $n_i$ 的宇宙。由于每次跳跃需要巨大的能量，所以每次牛妹只能跳跃不超过 $1500$ 次。

输入格式

第一行三个整数 $q, d, l$，以空格分离。

接下来 $q$ 行，第 $i$ 行一个整数 $n_i$，表示目的地宇宙的编号。

输出格式

输出 $q$ 行，第 $i$ 行输出 $k_i,o_{i,0},o_{i,1} \ldots o_{i,k_i}$。

其中 $o_{i,0}=1$，$o_{i,k_i}=n_i$，且可以通过三种空间跳跃技术之一从编号为 $o_{i,j}$ 的宇宙跳跃到编号为 $o_{i,j+1}$ 的宇宙。

输出需要满足对于任意的 $1 \le i \le q$ 和 $0 \le j \le k_i$，$0\le k_i\le 1500$，$-10^{18}\le o_{i,j}\le 10^{18}$。

输出任意一组满足上述所有条件的解即可，数据保证至少存在一组满足上述所有条件的解。

样例

5 3 10000
10
-9
0
-7
1

6 1 2 4 8 16 13 10
4 1 0 -3 -6 -9
1 1 0
5 1 -2 -5 -10 -20 -7
0 1

数据范围

• 对于 $10\%$ 的数据，满足 $|n_i|\le 10^3$，$d=1$，$l=1500$。
• 对于 $30\%$ 的数据，满足 $|n_i|\le 10^3$。
• 对于另外 $10\%$ 的数据，满足 $|n_i|\le 10^6$，$l=10^6$。
• 对于另外 $20\%$ 的数据，满足 $|n_i|\le 10^6$。
• 对于 $100\%$ 的数据，满足 $|n_i|\le 10^7$，$1\le q\le 20$，$1\le d\le 10^6$，$10^3\le l\le 10^6$。