Konstruiere für ein gegebenes $K$ zwei nichtleere Binärzeichenketten $S$ und $T$ mit jeweils höchstens $8848$ Zeichen, die genau $K$ verschiedene längste gemeinsame Teilfolgen haben. Formal: Ist $L$ die Länge der längsten gemeinsamen Teilfolge von $S$ und $T$, so sollen genau $K$ verschiedene Binärzeichenketten der Länge $L$ existieren, die sowohl Teilfolgen von $S$ als auch von $T$ sind.

Es ist garantiert, dass solche Zeichenketten unter den Beschränkungen dieser Aufgabe immer existieren.

Eingabe

Die einzige Eingabezeile enthält eine ganze Zahl $K$ ($1\le K\le 10^9$).

Ausgabe

Gib die nichtleeren Binärzeichenketten $S$ und $T$ in getrennten Zeilen aus. Ihre Längen dürfen jeweils $8848$ nicht überschreiten. Sie dürfen unterschiedliche Längen haben.

Falls es mehrere Lösungen gibt, darfst du eine beliebige davon ausgeben.

Beispiele

Eingabe 1

1

Ausgabe 1

1111
00

Eingabe 2

2

Ausgabe 2

10
01

Eingabe 3

3

Ausgabe 3

010
1001

Eingabe 4

100

Ausgabe 4

10001000001011100001010100011
11000010001010101001010011100

Hinweis

Im ersten Beispiel hat die längste gemeinsame Teilfolge von 1111 und 00 die Länge $0$. Es gibt nur eine Zeichenkette der Länge $0$, die eine Teilfolge beider ist: die leere Zeichenkette.

Im zweiten Beispiel beträgt die Länge der längsten gemeinsamen Teilfolge der Zeichenketten 10 und 01 genau $1$, und es gibt $2$ Zeichenketten der Länge $1$, die sowohl Teilfolgen von $S$ als auch von $T$ sind: 0 und 1.

Im zweiten Beispiel beträgt die Länge der längsten gemeinsamen Teilfolge der Zeichenketten 010 und 1001 genau $2$, und es gibt $3$ Zeichenketten der Länge $2$, die sowohl Teilfolgen von $S$ als auch von $T$ sind: 00, 01 und 10.

Zeichenketten länger als der Everest zu machen, wäre respektlos…