Город Макао называют «Монте-Карло Востока». В Макао работают более тридцати казино, приманивающих ежегодно миллионы игроков как из Китая, так и из других стран. Индустрия азартных игр формирует около 40% ВВП города.

От своих друзей из Гуанчжоу Вова узнал, что в Макао есть специальные казино, в которых играют только программисты. Это показалось Вове очень интересным, и он решил непременно сходить в такое казино. Одно из подобных заведений было расположено неподалёку от отеля, где остановился Вова, поэтому вечером он, пополнив запас наличных денег, пошёл в казино.

За игровыми столами в казино, по-видимому, и вправду сидели программисты, потому что ни карт, ни фишек на столах не было, но перед каждым игроком лежал блокнот, в который тот записывал какие-то числа. Как пояснили Вове, смысл игры заключался в следующем. Сначала каждый игрок записывал на чистом листе блокнота одну единицу. После этого крупье начинал зачитывать последовательность из нулей и единиц, называя по одной цифре. Если крупье называл ноль, все игроки дописывали ноль в конец последнего числа, выписанного на их листе. Если же крупье называл единицу, то игрок мог либо дописать эту единицу в конец последнего числа, либо записать её в новой строке, начав тем самым с неё новое число. После того как крупье прекращал зачитывать цифры, каждый игрок переводил все записанные им двоичные числа в десятичный вид, затем склеивал их все в одно десятичное число в том порядке, в котором они были записаны. Выигрывал тот игрок, который получал в результате наименьшее число.

Например, если крупье зачитал последовательность 1011100101, первый игрок записал двоичные числа 1, 1011 и 100101 (десятичные 1, 11 и 37), а второй игрок записал 110, 11100 и 101 (десятичные 6, 28 и 5), то победу одержал второй игрок, поскольку 6285 меньше 11137.

Перед тем как сесть за игровой стол, Вова решил научиться оптимально играть для простого случая, когда последовательность крупье представляет собой запись в двоичном виде всех целых чисел подряд от 2 до n (в разобранном выше примере n равнялось пяти). Но быстро придумать оптимальную стратегию Вова не смог, поэтому он обратился за помощью к вам.

В единственной строке записано целое число n (2 ≤ n ≤ 100 000).

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

В примере нужно записать все цифры, зачитанные крупье, во второе число. В этом случае после перевода чисел в десятичную систему и их склейки получится число 1741.