CF1166D.Cute Sequences

Given a positive integer $m$, we say that a sequence $x_1, x_2, \dots, x_n$ of positive integers is $m$-cute if for every index $i$ such that $2 \le i \le n$ it holds that $x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i$ for some positive integer $r_i$ satisfying $1 \le r_i \le m$.

You will be given $q$ queries consisting of three positive integers $a$, $b$ and $m$. For each query you must determine whether or not there exists an $m$-cute sequence whose first term is $a$ and whose last term is $b$. If such a sequence exists, you must additionally find an example of it.

给定一个正整数 $m$，我们称一个正整数序列 $x_1, x_2, \dots, x_n$ 是 $m$-cute 的，如果对每个满足 $2 \le i \le n$ 的下标 $i$，均存在某个满足 $1 \le r_i \le m$ 的正整数 $r_i$，使得

$$x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i.$$

你将收到 $q$ 个查询，每个查询包含三个正整数 $a$、$b$ 和 $m$。对每个查询，你必须判断：是否存在一个 $m$-cute 序列，其首项为 $a$、末项为 $b$。若存在，你还须给出这样一个序列的一个具体例子。

The first line contains an integer number $q$ ($1 \le q \le 10^3$) — the number of queries.

Each of the following $q$ lines contains three integers $a$, $b$, and $m$ ($1 \le a, b, m \le 10^{14}$, $a \leq b$), describing a single query.

第一行包含一个整数 $q$（$1 \le q \le 10^3$），表示查询次数。

接下来的 $q$ 行，每行包含三个整数 $a$、$b$ 和 $m$（$1 \le a, b, m \le 10^{14}$，且 $a \leq b$），描述一次查询。

For each query, if no $m$-cute sequence whose first term is $a$ and whose last term is $b$ exists, print $-1$.

Otherwise print an integer $k$ ($1 \le k \leq 50$), followed by $k$ integers $x_1, x_2, \dots, x_k$ ($1 \le x_i \le 10^{14}$). These integers must satisfy $x_1 = a$, $x_k = b$, and that the sequence $x_1, x_2, \dots, x_k$ is $m$-cute.

It can be shown that under the problem constraints, for each query either no $m$-cute sequence exists, or there exists one with at most $50$ terms.

If there are multiple possible sequences, you may print any of them.

对于每个查询，如果不存在首项为 $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$-cute 的。

可以证明，在本题的约束条件下，对每个查询，要么不存在 $m$-cute 序列，要么存在一个长度至多为 $50$ 的 $m$-cute 序列。

若存在多个可能的序列，输出任意一个即可。

Consider the sample. In the first query, the sequence $5, 6, 13, 26$ is valid since $6 = 5 + \bf{\color{blue} 1}$, $13 = 6 + 5 + {\bf\color{blue} 2}$ and $26 = 13 + 6 + 5 + {\bf\color{blue} 2}$ have the bold values all between $1$ and $2$, so the sequence is $2$-cute. Other valid sequences, such as $5, 7, 13, 26$ are also accepted.

In the second query, the only possible $1$-cute sequence starting at $3$ is $3, 4, 8, 16, \dots$, which does not contain $9$.

考虑样例。在第一个查询中，序列 $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$-cute 的。其他合法序列（例如 $5, 7, 13, 26$）也同样被接受。

在第二个查询中，唯一可能的以 $3$ 开头的 $1$-cute 序列为 $3, 4, 8, 16, \dots$，该序列不包含 $9$。