← 返回题目列表

Codeforces · 1166/D

D. 可爱的序列

中文机器翻译题面 查看原题

给定一个正整数 $$$m$$$,我们说正整数序列 $$$x_1, x_2, \dots, x_n$$$ 是 $$$m$$$-cute,如果对于每个索引 $$$i$$$ 使得 $$$2 \le i \le n$$$ 保持 $$$x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i$$$ 对于某个正整数 $$$r_i$$$ 满足 $$$1 \le r_i \le m$$$。

您将收到由三个正整数 $$$a$$$、$$$b$$$ 和 $$$m$$$ 组成的 $$$q$$$ 查询。对于每个查询,您必须确定是否存在 $$$m$$$-cute 序列,其第一项是 $$$a$$$,最后一项是 $$$b$$$。如果存在这样的序列,您还必须找到它的示例。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^3$$$) — 查询数。

以下 $$$q$$$ 行中的每一行都包含三个整数 $$$a$$$、$$$b$$$ 和 $$$m$$$ ($$$1 \le a, b, m \le 10^{14}$$$, $$$a \leq b$$$),描述单个查询。

输出

对于每个查询,如果不存在第一项为 $$$a$$$、最后一项为 $$$b$$$ 的 $$$m$$$-cute 序列,则打印 $$$-1$$$。

否则打印一个整数 $$$k$$$ ($$$1 \le k \leq 50$$$),后跟 $$$k$$$ 整数 $$$x_1, x_2, \dots, x_k$$$ ($$$1 \le x_i \le 10^{14}$$$)。这些整数必须满足 $$$x_1 = a$$$, $$$x_k = b$$$,并且序列 $$$x_1, x_2, \dots, x_k$$$ 是 $$$m$$$-可爱的。

可以证明,在问题约束下,对于每个查询,要么不存在 $$$m$$$-cute 序列,要么存在最多包含 $$$50$$$ 项的序列。

如果有多个可能的序列,您可以打印其中任何一个。

示例

输入 #1

2
5 26 2
3 9 1

输出 #1

4 5 6 13 26
-1

注意

考虑示例。在第一个查询中,序列 $$$5, 6, 13, 26$$$ 有效,因为 $$$6 = 5 + \bf{\color{blue} 1}$$$、$$$13 = 6 + 5 + {\bf\color{blue} 2}$$$ 和 $$$26 = 13 + 6 + 5 + {\bf\color{blue} 2}$$$ 的粗体值均位于$$$1$$$ 和 $$$2$$$,所以序列是$$$2$$$-可爱。其他有效序列,例如 $$$5, 7, 13, 26$$$ 也被接受。

在第二个查询中,从 $$$3$$$ 开始的唯一可能的 $$$1$$$-cute 序列是 $$$3, 4, 8, 16, \dots$$$,其中不包含 $$$9$$$。