Nous savons tous 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}$ est un nombre entier pour tout $0 \le k \le n$. Mais il serait intéressant de pouvoir le prouver en fournissant un couplage entre les facteurs du numérateur et ceux du dénominateur, n'est-ce pas ?

Construisons un graphe biparti avec $k$ sommets dans chaque partie. Le $i$-ième sommet de la partie gauche correspond au facteur $(n + 1 - i)$ du numérateur et le $j$-ième sommet de la partie droite correspond au facteur $j$ du dénominateur. Il existe une arête $i - j$ si et seulement si $j$ divise $(n + 1 - i)$. Le nombre $k$ est dit prouvable pour $n$ s'il existe un couplage parfait dans ce graphe biparti.

Étant donné $n$, vérifiez si $k$ est prouvable pour chaque $k$ satisfaisant $0 \le k \le n$.

Entrée

La seule ligne contient un entier $n$ ($0 \le n \le 10^{18}$).

Sortie

Imprimez une chaîne de longueur $(n + 1)$ composée de « 0 » et de « 1 », où le $(k + 1)$-ième caractère doit être « 1 » si et seulement si $k$ est prouvable pour $n$.

Vous pensez que cela provoquera une erreur de dépassement de limite de sortie (Output Limit Exceeded) ? Hmm... D'accord. Compressons la chaîne.

Soient $s_0 = \text{« 0 »}$ et $s_1 = \text{« 1 »}$. Vous pouvez définir $s_2, s_3, \dots, s_t$. La chaîne $s_i$ doit être une concaténation de plusieurs chaînes définies précédemment. Formellement, $\forall i(2 \le i \le t) : s_i = s_{j_1} + s_{j_2} + \dots + s_{j_{k_i}}$, où $1 \le k_i$ et $\forall r(1 \le r \le k_i) : j_r < i$. La chaîne $s_t$ doit être la réponse au problème.

Sur la première ligne, imprimez un entier $t$ ($2 \le t \le 500$).

Sur les $t - 1$ lignes suivantes, imprimez les descriptions de $s_i$. Chaque description doit avoir la forme $k_i \ j_1 \ j_2 \ \dots \ j_{k_i}$, avec $1 \le k_i$ et $0 \le j_r < i$.

La longueur totale de toutes les descriptions ne doit pas dépasser $10\,000$ : $\sum_{i=2}^{t} k_i \le 10\,000$.

Nous pouvons montrer que pour tous les tests valides, il existe un moyen de construire la chaîne de réponse en respectant toutes les limitations. S'il existe plusieurs façons possibles de le faire, imprimez-en une quelconque. Notez que vous n'avez pas besoin de minimiser $t$ ou la longueur totale de toutes les descriptions.

Exemples

Entrée 1

1

Sortie 1

2
2 1 1

Entrée 2

0

Sortie 2

2
1 1

Entrée 3

7

Sortie 3

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

Remarque

Dans le troisième exemple : $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 »}$.