Дано целое число \(x\). Вам нужно уменьшить \(x\) до \(1\).
Для этого вы можете выполнять следующую операцию несколько (возможно, ноль) раз:
- выбрать \(d\), являющееся делителем \(x\), затем заменить \(x\) на \(x-d\), т.е. уменьшить \(x\) на \(d\). (Мы называем \(d\) делителем \(x\), если \(d\) — положительное целое число, для которого существует целое \(q\), такое что \(x = d \cdot q\).)
Кроме того, есть дополнительное ограничение: вам нельзя выбирать одно и то же значение \(d\) более двух раз.
Например, для \(x=5\) следующая последовательность действий является недопустимой, поскольку в ней \(1\) использована более чем дважды: \(5\xrightarrow{-1}4\xrightarrow{-1}3\xrightarrow{-1}2\xrightarrow{-1}1\). Однако следующая последовательность действий является допустимой: \(5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1\).
Выведите произвольную последовательность действий, которая уменьшает \(x\) до \(1\) не более чем за \(1000\) операций. Можно доказать, что такая последовательность всегда существует.
Выходные данные
Для каждого набора входных данных выведите две строки.
В первой строке выведите целое число \(k\) (\(1 \le k \le 1001\)).
Во второй строке через пробел выведите \(k\) целых чисел \(a_1,a_2,\ldots,a_k\), таких что:
- \(a_1=x\);
- \(a_k=1\);
- для каждого \(2 \le i \le k\), величина \((a_{i-1}-a_i)\) является делителем \(a_{i-1}\). Каждое число может быть выбрано делителем не более чем дважды.
Примечание
В первом наборе входных данных можно выполнить следующую последовательность операций: \(3\xrightarrow{-1}2\xrightarrow{-1}1\).
В втором наборе входных данных можно выполнить следующую последовательность операций: \(5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1\).
В третьем наборе входных данных можно выполнить следующую последовательность операций: \(14\xrightarrow{-2}12\xrightarrow{-6}6\xrightarrow{-3}3\xrightarrow{-1}2\xrightarrow{-1}1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
5
14
|
3
3 2 1
4
5 4 2 1
6
14 12 6 3 2 1
|