B. Кошачье преобразование фурфурье
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кошачье преобразование фурфурье это популярный алгоритм в программировании, использующийся при создании длинных кошек. Неко хочет применить этот алгоритм, чтобы создать идеальную длинную кошку.

Предположим у нас есть кошка с целым числом $$$x$$$. Идеальная длинная кошка это кошка с числом равным $$$2^m - 1$$$ для некоторого неотрицательного $$$m$$$. Например числа $$$0$$$, $$$1$$$, $$$3$$$, $$$7$$$, $$$15$$$ подходят для идеальных длинных кошек.

В кошачьем преобразовании фурфурье можно менять $$$x$$$ используя следующие операции:

  • (Операция А): вы выбираете произвольное неотрицательное число $$$n$$$ и заменяете $$$x$$$ на $$$x \oplus (2^n - 1)$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
  • (Операция Ы): заменить $$$x$$$ на $$$x + 1$$$.

Первая применённая операция должна быть типа А, вторая операция — типа Ы, третья снова типа А, и так далее. Формально, если пронумеровать операции с единицы в порядке их выполнения, то операции с нечётным номером должны быть типа А, а операции с чётным номером — типа Ы.

Неко хочет производит идеальных длинных кошек в промышленном масштабе, поэтому на одну кошку он может потратить не более $$$40$$$ операций. Можете ли вы ему помочь и составить план операций, которые нужно проделать?

Обратите внимание, что не требуется минимизировать число выполненных операций. Достаточно лишь, чтобы число операций не превосходило $$$40$$$.

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

Единственная строка содержит одно целое число $$$x$$$ ($$$1 \le x \le 10^6$$$).

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

В первой строке выведите одно целое число $$$t$$$ ($$$0 \le t \le 40$$$) — количество операций, которое нужно применить.

Затем для каждой операции с нечётным номером выведите соответствующее число $$$n_i$$$ в ней. В частности, выведите $$$\lceil \frac{t}{2} \rceil$$$ целых чисел $$$n_i$$$ ($$$0 \le n_i \le 30$$$), обозначающих замену $$$x$$$ на $$$x \oplus (2^{n_i} - 1)$$$ в соответствующем шаге.

В случае если существует несколько возможных ответов, выведите любой из них. Можно показать, что в ограничениях задачи существует хотя бы один возможный ответ.

Примеры
Входные данные
39
Выходные данные
4
5 3
Входные данные
1
Выходные данные
0
Входные данные
7
Выходные данные
0
Примечание

В первом примере один из возможных способов преобразовывать число выглядит следующим образом: $$$39 \to 56 \to 57 \to 62 \to 63$$$. Или более подробно:

  1. Выбираем $$$n = 5$$$. $$$x$$$ заменяется на $$$39 \oplus 31$$$, то есть $$$56$$$.
  2. Увеличиваем $$$x$$$ на $$$1$$$, тем самым он становится равным $$$57$$$.
  3. Выбираем $$$n = 3$$$. $$$x$$$ заменяется на $$$57 \oplus 7$$$, то есть $$$62$$$.
  4. Увеличиваем $$$x$$$ на $$$1$$$, тем самым он становится равным $$$63 = 2^6 - 1$$$.

Во втором и третьем примере число можно не преобразовывать.