Wir wissen alle, dass $\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}$ für jedes $0 \le k \le n$ eine ganze Zahl ist. Aber wäre es nicht schön, dies durch eine Zuordnung der Faktoren im Zähler zu denen im Nenner beweisen zu können?

Bauen wir einen bipartiten Graphen mit $k$ Knoten in jeder der beiden Mengen. Der $i$-te Knoten der linken Menge entspricht dem Faktor $n+1-i$ im Zähler, und der $j$-te Knoten der rechten Menge entspricht dem Faktor $j$ im Nenner. Genau dann, wenn $j$ ein Teiler von $n+1-i$ ist, gibt es eine Kante $i-j$. Die Zahl $k$ heißt für $n$ beweisbar, wenn dieser bipartite Graph ein perfektes Matching besitzt.

Prüfen Sie für ein gegebenes $n$ für jedes $k$ mit $0 \le k \le n$, ob $k$ beweisbar ist.

Eingabe

Die einzige Zeile enthält eine ganze Zahl $n$ ($0 \le n \le 10^{18}$).

Ausgabe

Geben Sie eine Zeichenkette der Länge $n+1$ aus Nullen und Einsen aus. Ihr $(k+1)$-tes Zeichen soll genau dann 1 sein, wenn $k$ für $n$ beweisbar ist.

Was, Sie glauben, das überschreitet das Ausgabelimit? Hmmmm ... Na gut. Komprimieren wir die Zeichenkette.

Seien $s_0=\text{„0“}$ und $s_1=\text{„1“}$. Sie dürfen $s_2,s_3,\ldots,s_t$ definieren. Die Zeichenkette $s_i$ soll eine Verkettung mehrerer zuvor definierter Zeichenketten sein. Formal gilt $\forall i\ (2 \le i \le t):\ s_i=s_{j_1}+s_{j_2}+\ldots+s_{j_{k_i}}$, wobei $1 \le k_i$ und $\forall r\ (1 \le r \le k_i):\ j_r<i$ gelten. Die Zeichenkette $s_t$ soll die Antwort auf die Aufgabe sein.

Geben Sie in der ersten Zeile eine ganze Zahl $t$ aus ($2 \le t \le 500$).

Geben Sie in den nächsten $t-1$ Zeilen die Beschreibungen von $s_i$ aus. Jede Beschreibung soll die Form $k_i\ j_1\ j_2\ \ldots\ j_{k_i}$ haben, mit $1 \le k_i$ und $0 \le j_r<i$.

Die Gesamtlänge aller Beschreibungen darf $10\,000$ nicht überschreiten: $\sum_{i=2}^{t} k_i \le 10\,000$.

Es lässt sich zeigen, dass für alle gültigen Testfälle eine Konstruktion der Antwortzeichenkette existiert, die alle Beschränkungen einhält. Gibt es mehrere Möglichkeiten, geben Sie eine beliebige davon aus. Sie müssen weder $t$ noch die Gesamtlänge aller Beschreibungen minimieren.

Beispiele

Eingabe 1

1

Ausgabe 1

2
2 1 1

Eingabe 2

0

Ausgabe 2

2
1 1

Eingabe 3

7

Ausgabe 3

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

Hinweis

Im dritten Beispiel gilt: $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“}$.