Масив і знову додавання

Є масив $a$, елементи якого пронумеровані від $1$ до $100$. Початково $a_i=0$ для $1\le i<100$, а останній елемент $a_{100}$ рівний $1$.

Масив $a$ можна змінювати, використовуючи операції збільшення. Для того, щоб виконати $m$ операцій збільшення, необхідно вибрати $m$ цілих чисел $p_1,p_2,\dots ,p_m$ ($1\le p_i<100$) та послідовно виконати операції присвоєння $a_{p_i}\leftarrow (a_{p_i}+a_{p_i+1})$ для $i$ від $1$ до $m$.

Задано ціле число $n$. Знайдіть послідовність операцій збільшення, після виконання яких елемент на першій позиції в масиві $a$ стане рівним $n$.

Вхідні дані

У першому рядку задано два цілі числа $t$, $g$ ($1\le t\le 100$, $0\le g\le 5$) — кількість наборів вхідних даних та номер блоку тестів відповідно.

У наступних $t$ рядках задано по одному цілому числу $n$ ($1\le n\le 10^{18}$) — значенню, якому повинно дорівнювати $a_1$ після виконання операцій збільшення в черговому наборі.

Вихідні дані

Для кожного набору вхідних даних у першому рядку виведіть одне ціле число $m$ ($0\le m\le 2000$) — кількість операцій збільшення.

У другому рядку виведіть $m$ цілих чисел $p_i$ ($1\le p_i<100$) — параметри операцій збільшення.

Якщо існує кілька правильних відповідей, дозволяється вивести будь-яку з них.

Приклади

1 0
1

99
99 98 ... 7 6 5 4 3 2 1

2 0
3
16

101
99 98 ... 7 6 5 4 3 2 1 1 1
103
99 98 ... 7 6 5 4 4 3 3 2 2 1 1

Примітка

Для наочності приклади вихідних даних в умові зменшено: для отримання правильної відповіді необхідно замінити «...» на послідовність цілих чисел від $97$ до $8$.

Розглянемо другий набір вхідних даних другого прикладу $n=16$. Перші 8 елементів масиву $a$ після виконання чергової операції виглядають наступним чином:

• $p_1$ = 99, $a=[0,0,0,0,0,0,0,0,\dots ,0,0,1,1]$;

• $p_2$ = 98, $a=[0,0,0,0,0,0,0,0,\dots ,0,1,1,1]$;

• $\dots$

• $p_{93}=7$, $a=[0,0,0,0,0,0,1,1,\dots ,1,1,1,1]$;

• $p_{94}=6$, $a=[0,0,0,0,0,1,1,1,\dots ,1,1,1,1]$;

• $p_{95}=5$, $a=[0,0,0,0,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{96}=4$, $a=[0,0,0,1,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{97}=4$, $a=[0,0,0,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{98}=3$, $a=[0,0,2,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{99}=3$, $a=[0,0,4,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{100}=2$, $a=[0,4,4,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{101}=2$, $a=[0,8,4,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{102}=1$, $a=[8,8,4,2,1,1,1,1,\dots ,1,1,1,1]$;

• $p_{103}=1$, $a=[16,8,4,2,1,1,1,1,\dots ,1,1,1,1]$.

Оцінювання

У перших чотирьох блоках тестів дозволяється використати не більше ніж 300 операцій збільшення.

1. ($4$ бали): $n\le 100$;

2. ($6$ балів): $n=k^2$ для деякого цілого $1\le k\le 100$;

3. ($10$ балів): $n=(2^k-1)$ для деякого цілого $k$;

4. ($13$ балів): $n$ — число Фібоначчі ($n$ є одним з елементів послідовності, де кожен елемент є сумою двох попередніх: $1,1,2,3,5,8,13,21,34,\dots$);

5. (до $67$ балів): без додаткових обмежень. Нехай максимальна кількість використаних операцій збільшення дорівнює $c$. Якщо $c\le 300$, то ви отримаєте $67$ балів, а інакше ви отримаєте ($17+\lfloor \frac{2000-c}{34}\rfloor$) балів.

Код на мові C++, який обчислює кількість балів за останній блок тестів залежно від кількості використаних операцій збільшення:

((c <= 300) ? 67 : (17 + (2000 - c) / 34))