Todos sabemos que $\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}$ é um inteiro para qualquer $0 \le k \le n$. Mas seria bom poder prová-lo fornecendo um emparelhamento entre os fatores do numerador e do denominador, não seria?

Vamos construir um grafo bipartido com $k$ vértices em cada parte. O $i$-ésimo vértice da parte esquerda corresponde ao fator $(n+1-i)$ do numerador, e o $j$-ésimo vértice da parte direita corresponde ao fator $j$ do denominador. Existe uma aresta $i-j$ se e só se $j$ dividir $(n+1-i)$. O número $k$ é demonstrável para $n$ se existir um emparelhamento perfeito neste grafo bipartido.

Dado $n$, verifique se $k$ é demonstrável para cada $k$ que satisfaça $0 \le k \le n$.

Entrada

A única linha contém um inteiro $n$ ($0 \le n \le 10^{18}$).

Saída

Imprima uma cadeia de comprimento $(n+1)$ composta por 0 e 1; o $(k+1)$-ésimo carácter deve ser 1 se e só se $k$ for demonstrável para $n$.

O quê, acha que isto vai dar Limite de Saída Excedido? Hummm... Está bem. Vamos comprimir a cadeia.

Sejam $s_0=$"0" e $s_1=$"1". Pode definir $s_2,s_3,\ldots,s_t$. A cadeia $s_i$ deve ser uma concatenação de várias cadeias definidas anteriormente. Formalmente, $\forall i\ (2 \le i \le t): s_i=s_{j_1}+s_{j_2}+\ldots+s_{j_{k_i}}$, onde $1 \le k_i$ e $\forall r\ (1 \le r \le k_i): j_r<i$. A cadeia $s_t$ deve ser a resposta ao problema.

Na primeira linha, imprima um inteiro $t$ ($2 \le t \le 500$).

Nas $t-1$ linhas seguintes, imprima as descrições de $s_i$. Cada descrição deve ter a forma $k_i\ j_1\ j_2\ \ldots\ j_{k_i}$, com $1 \le k_i$ e $0 \le j_r < i$.

O comprimento total de todas as descrições não deve exceder $10\,000$: $\sum_{i=2}^{t} k_i \le 10\,000$.

Podemos mostrar que, para todos os testes válidos, existe uma maneira de construir a cadeia resposta respeitando todos os limites. Se existirem várias maneiras possíveis, imprima qualquer uma delas. Note que não é necessário minimizar $t$ nem o comprimento total das descrições.

Exemplos

Entrada 1

1

Saída 1

2
2 1 1

Entrada 2

0

Saída 2

2
1 1

Entrada 3

7

Saída 3

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

Nota

No terceiro exemplo: $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”}$.