Мы все знаем, что $\binom{n}{k} = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+2) \cdot (n-k+1)}{1 \cdot 2 \cdot \dots \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$ доказуемым для каждого $k$, удовлетворяющего $0 \le k \le n$.

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

Единственная строка содержит одно целое число $n$ ($0 \le n \le 10^{18}$).

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

Выведите строку длины $(n + 1)$, состоящую из символов «0» и «1», где $(k + 1)$-й символ должен быть «1» тогда и только тогда, когда $k$ доказуемо для $n$.

Думаете, это приведет к ошибке Output Limit Exceeded? Хмм... Хорошо. Давайте сожмем строку.

Пусть $s_0 = \text{“0”}$ и $s_1 = \text{“1”}$. Вы можете определить $s_2, s_3, \dots, s_t$. Строка $s_i$ должна быть конкатенацией нескольких ранее определенных строк. Формально, $\forall i(2 \le i \le t) : s_i = s_{j_1} + s_{j_2} + \dots + 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 \dots 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

2
2 1 1

Пример 2

0

2
1 1

Пример 3

7

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”}$.