D. Милые последовательности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть зафиксировано целое положительное число $$$m$$$. Мы называем последовательность $$$x_1, x_2, \dots, x_n$$$ положительных чисел $$$m$$$-милой, если для всех индексов $$$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$$$.

Вам даны $$$q$$$ запросов, каждый из которых описывается тремя целыми числами $$$a$$$, $$$b$$$ и $$$m$$$. Для каждого запроса нужно определить, существует ли $$$m$$$-милая последовательность, первый член которой равен $$$a$$$, а последний равен $$$b$$$. Если такая последовательность существует, вы должны найти пример такой последовательности.

Входные данные

Первая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 10^3$$$) — количество запросов.

Каждая из следущих $$$q$$$ строк содержит три целых числа $$$a$$$, $$$b$$$ и $$$m$$$ ($$$1 \le a, b, m \le 10^{14}$$$, $$$a \leq b$$$), описывающих один запрос.

Выходные данные

Для каждого запроса, если $$$m$$$-милой последовательности, первый член которой равен $$$a$$$, а последний — $$$b$$$ не существует, выведите $$$-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$$$-милой последовательности, либо существует такая, которая содержит не более $$$50$$$ членов.

Если существуют несколько решений, выведите любое из них.

Пример
Входные данные
2
5 26 2
3 9 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$$$, они тоже будут приняты.

Во втором примере единственная $$$1$$$-милая последовательность, начинающаяся с $$$3$$$, это $$$3, 4, 8, 16, \dots$$$, она не содержит числа $$$9$$$.