Todos sabemos que $\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}$ es un número entero para cualquier $0 \le k \le n$. Pero sería bueno si pudiéramos probarlo proporcionando una correspondencia entre los factores del numerador y del denominador, ¿no es así?

Construyamos un grafo bipartito con $k$ vértices en cada parte. El $i$-ésimo vértice en la parte izquierda corresponde al factor $(n + 1 - i)$ del numerador y el $j$-ésimo vértice en la parte derecha corresponde al factor $j$ del denominador. Existe una arista $i - j$ si y solo si $j$ divide a $(n + 1 - i)$. El número $k$ es demostrable para $n$ si existe un emparejamiento perfecto en este grafo bipartito.

Dado $n$, verifique si $k$ es demostrable para cada $k$ que satisface $0 \le k \le n$.

Entrada

La única línea contiene un entero $n$ ($0 \le n \le 10^{18}$).

Salida

Imprima una cadena de longitud $(n + 1)$ que consista en '0' y '1', donde el $(k + 1)$-ésimo carácter debe ser '1' si y solo si $k$ es demostrable para $n$.

¿Qué, crees que esto causará un Output Limit Exceeded? Mmm... Está bien. Comprimamos la cadena.

Sean $s_0 = \text{"0"}$ y $s_1 = \text{"1"}$. Puede definir $s_2, s_3, \dots, s_t$. La cadena $s_i$ debe ser una concatenación de varias cadenas definidas anteriormente. Formalmente, $\forall i(2 \le i \le t) : s_i = s_{j_1} + s_{j_2} + \dots + s_{j_{k_i}}$, donde $1 \le k_i$ y $\forall r(1 \le r \le k_i) : j_r < i$. La cadena $s_t$ debe ser la respuesta al problema.

En la primera línea, imprima un entero $t$ ($2 \le t \le 500$).

En las siguientes $t - 1$ líneas, imprima las descripciones de $s_i$. Cada descripción debe tener la forma $k_i \ j_1 \ j_2 \ \dots \ j_{k_i}$, con $1 \le k_i$ y $0 \le j_r < i$.

La longitud total de todas las descripciones no debe exceder $10\,000$: $\sum_{i=2}^t k_i \le 10\,000$.

Podemos demostrar que para todas las pruebas válidas existe una forma de construir la cadena de respuesta cumpliendo todas las limitaciones. Si hay varias formas posibles de hacerlo, imprima cualquiera de ellas. Tenga en cuenta que no tiene que minimizar $t$ ni la longitud total de todas las descripciones.

Ejemplos

Entrada 1

1

Salida 1

2
2 1 1

Entrada 2

0

Salida 2

2
1 1

Entrada 3

7

Salida 3

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

Nota

En el tercer ejemplo: $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"}$.