Кошачье преобразование фурфурье это популярный алгоритм в программировании, использующийся при создании длинных кошек. Неко хочет применить этот алгоритм, чтобы создать идеальную длинную кошку.
Предположим у нас есть кошка с целым числом \(x\). Идеальная длинная кошка это кошка с числом равным \(2^m - 1\) для некоторого неотрицательного \(m\). Например числа \(0\), \(1\), \(3\), \(7\), \(15\) подходят для идеальных длинных кошек.
В кошачьем преобразовании фурфурье можно менять \(x\) используя следующие операции:
- (Операция А): вы выбираете произвольное неотрицательное число \(n\) и заменяете \(x\) на \(x \oplus (2^n - 1)\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
- (Операция Ы): заменить \(x\) на \(x + 1\).
Первая применённая операция должна быть типа А, вторая операция — типа Ы, третья снова типа А, и так далее. Формально, если пронумеровать операции с единицы в порядке их выполнения, то операции с нечётным номером должны быть типа А, а операции с чётным номером — типа Ы.
Неко хочет производит идеальных длинных кошек в промышленном масштабе, поэтому на одну кошку он может потратить не более \(40\) операций. Можете ли вы ему помочь и составить план операций, которые нужно проделать?
Обратите внимание, что не требуется минимизировать число выполненных операций. Достаточно лишь, чтобы число операций не превосходило \(40\).
Выходные данные
В первой строке выведите одно целое число \(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 \to 56 \to 57 \to 62 \to 63\). Или более подробно:
- Выбираем \(n = 5\). \(x\) заменяется на \(39 \oplus 31\), то есть \(56\).
- Увеличиваем \(x\) на \(1\), тем самым он становится равным \(57\).
- Выбираем \(n = 3\). \(x\) заменяется на \(57 \oplus 7\), то есть \(62\).
- Увеличиваем \(x\) на \(1\), тем самым он становится равным \(63 = 2^6 - 1\).
Во втором и третьем примере число можно не преобразовывать.