Усі ми знаємо, що $\binom{n}{k}=\frac{n\cdot(n-1)\cdot\ldots\cdot(n-k+2)\cdot(n-k+1)}{1\cdot2\cdot\ldots\cdot(k-1)\cdot k}$ є цілим числом для будь-яких $0 \le k \le n$. Але було б добре довести це, зіставивши множники чисельника та знаменника, чи не так?

Побудуймо двочастковий граф із $k$ вершинами в кожній частці. $i$-та вершина лівої частки відповідає множнику $(n+1-i)$ у чисельнику, а $j$-та вершина правої — множнику $j$ у знаменнику. Ребро $i$—$j$ існує тоді й лише тоді, коли $j$ ділить $(n+1-i)$. Число $k$ називатимемо довідним для $n$, якщо в цьому двочастковому графі існує досконале паросполучення.

За заданим $n$ перевірте довідність кожного $k$, що задовольняє $0 \le k \le n$.

Вхідні дані

Єдиний рядок містить одне ціле число $n$ ($0 \le n \le 10^{18}$).

Вихідні дані

Виведіть рядок довжини $n+1$ із символів 0 і 1, у якому $(k+1)$-й символ дорівнює 1 тоді й лише тоді, коли $k$ довідне для $n$.

Що, думаєте, це призведе до перевищення обмеження на виведення? Гммм... Гаразд. Стиснімо рядок.

Нехай $s_0=\text{“0”}$ та $s_1=\text{“1”}$. Ви можете визначити $s_2,s_3,\ldots,s_t$. Рядок $s_i$ має бути конкатенацією кількох раніше визначених рядків. Формально, $\forall i\ (2 \le i \le t): s_i=s_{j_1}+s_{j_2}+\ldots+s_{j_{k_i}}$, де $1 \le k_i$ та $\forall r\ (1 \le r \le k_i): j_r<i$. Рядок $s_t$ має бути відповіддю на задачу.

У першому рядку виведіть одне ціле число $t$ ($2 \le t \le 500$).

У наступних $t-1$ рядках виведіть описи $s_i$. Кожен опис має вигляд $k_i\ j_1\ j_2\ \ldots\ j_{k_i}$, де $1 \le k_i$ та $0 \le j_r<i$.

Сумарна довжина всіх описів не повинна перевищувати $10\,000$: $\sum_{i=2}^{t} k_i \le 10\,000$.

Можна показати, що для всіх коректних тестів існує спосіб побудувати рядок відповіді, дотримуючись усіх обмежень. Якщо таких способів кілька, виведіть будь-який із них. Зверніть увагу, що мінімізувати $t$ або сумарну довжину всіх описів не потрібно.

Приклади

Вхідні дані 1

1

Вихідні дані 1

2
2 1 1

Вхідні дані 2

0

Вихідні дані 2

2
1 1

Вхідні дані 3

7

Вихідні дані 3

4
2 1 1
4 1 2 0 0
3 3 1 2

Примітка

У третьому прикладі: $s_2=s_1+s_1=\text{“1”}+\text{“1”}=\text{“11”}$, $s_3=s_1+s_2+s_0+s_0=\text{“1”}+\text{“11”}+\text{“0”}+\text{“0”}=\text{“11100”}$, $s_4=s_3+s_1+s_2=\text{“11100”}+\text{“1”}+\text{“11”}=\text{“11100111”}$.