Пусть зафиксировано целое положительное число \(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\). Если такая последовательность существует, вы должны найти пример такой последовательности.
Выходные данные
Для каждого запроса, если \(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\) членов.
Если существуют несколько решений, выведите любое из них.
Примечание
Рассмотрим первый пример. В первом запросе последовательность \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 26 2
3 9 1
|
4 5 6 13 26
-1
|