Diberikan $K$, buat dua string biner tak kosong $S$ dan $T$, masing-masing memiliki panjang paling banyak $8848$, sehingga keduanya memiliki tepat $K$ subsekuens bersama terpanjang yang berbeda. Secara lebih formal, jika $L$ adalah panjang subsekuens bersama terpanjang dari $S$ dan $T$, harus ada tepat $K$ string biner berbeda dengan panjang $L$ yang merupakan subsekuens dari $S$ maupun $T$.

Dijamin bahwa dengan batasan soal ini string seperti itu selalu ada.

Masukan

Satu-satunya baris masukan berisi sebuah bilangan bulat $K$ ($1\le K\le 10^9$).

Keluaran

Cetak string biner tak kosong $S$ dan $T$ pada baris terpisah. Panjang masing-masing tidak boleh melebihi $8848$. Keduanya boleh memiliki panjang berbeda.

Jika ada lebih dari satu solusi, Anda boleh mencetak salah satunya.

Contoh

Masukan 1

1

Keluaran 1

1111
00

Masukan 2

2

Keluaran 2

10
01

Masukan 3

3

Keluaran 3

010
1001

Masukan 4

100

Keluaran 4

10001000001011100001010100011
11000010001010101001010011100

Catatan

Pada contoh pertama, subsekuens bersama terpanjang dari 1111 dan 00 memiliki panjang $0$, dan hanya ada satu string sepanjang $0$ yang merupakan subsekuens keduanya, yaitu string kosong.

Pada contoh kedua, panjang subsekuens bersama terpanjang dari string 10 dan 01 adalah $1$, dan ada $2$ string sepanjang $1$ yang merupakan subsekuens dari $S$ maupun $T$: 0 dan 1.

Pada contoh kedua, panjang subsekuens bersama terpanjang dari string 010 dan 1001 adalah $2$, dan ada $3$ string sepanjang $2$ yang merupakan subsekuens dari $S$ maupun $T$: 00, 01, dan 10.

Membuat string yang lebih panjang daripada Everest akan terkesan tidak menghormatinya…