#P9648. 空间跳跃

    ID: 6267 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高逆向思考序列构造直接模拟路径恢复

空间跳跃

题目描述

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

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

  1. 如果当前在编号为 nn 的宇宙,且 min⁡(∣n∣,∣n−d∣)≤l\min(|n|,|n-d|)\le l,则她可以跳跃到编号为 n−dn − d 的宇宙,其中 dd 和 ll 都是给定的正整数。
  2. 如果当前在编号为 nn 的宇宙,则她可以跳跃到编号为 2×n2\times n 的宇宙。
  3. 如果当前在编号为 nn 的宇宙,且 n≡1(mod3)n\equiv1\pmod3,即 n=…,−5,−2,1,4,…n =\ldots , −5, −2,1,4, \ldots 时,她可以跳跃到编号为 n−13\frac{n-1}{3} 的宇宙。

牛妹一开始在编号为 11 的宇宙中,她可以随意的使用这三种空间跳跃技术在宇宙中跳跃。她有 qq 个想去的目的地 n1,n2,…,nqn_1, n_2, \ldots , n_q,她想知道对于每个 ii,她需要怎么从编号为 11 的宇宙跳跃到编号为 nin_i 的宇宙。由于每次跳跃需要巨大的能量,所以每次牛妹只能跳跃不超过 15001500 次。

输入格式

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

接下来 qq 行,第 ii 行一个整数 nin_i,表示目的地宇宙的编号。

输出格式

输出 qq 行,第 ii 行输出 ki,oi,0,oi,1…oi,kik_i,o_{i,0},o_{i,1} \ldots o_{i,k_i}。

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

输出需要满足对于任意的 1≤i≤q1 \le i \le q 和 0≤j≤ki0 \le j \le k_i,0≤ki≤15000\le k_i\le 1500,−1018≤oi,j≤1018-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%10\% 的数据,满足 ∣ni∣≤103|n_i|\le 10^3,d=1d=1,l=1500l=1500。
  • 对于 30%30\% 的数据,满足 ∣ni∣≤103|n_i|\le 10^3。
  • 对于另外 10%10\% 的数据,满足 ∣ni∣≤106|n_i|\le 10^6,l=106l=10^6。
  • 对于另外 20%20\% 的数据,满足 ∣ni∣≤106|n_i|\le 10^6。
  • 对于 100%100\% 的数据,满足 ∣ni∣≤107|n_i|\le 10^7,1≤q≤201\le q\le 20,1≤d≤1061\le d\le 10^6,103≤l≤10610^3\le l\le 10^6。