Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Cute Sequences

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGiven 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.

Input

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.

Output

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.

Example

Input

2 5 26 2 3 9 1

Output

4 5 6 13 26 -1

Note

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$$$.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2019 13:04:07 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|