Cho $K$, hãy xây dựng hai xâu nhị phân không rỗng $S$ và $T$, mỗi xâu có độ dài không quá $8848$, sao cho chúng có đúng $K$ dãy con chung dài nhất khác nhau. Chính xác hơn, nếu $L$ là độ dài dãy con chung dài nhất của $S$ và $T$, thì phải có đúng $K$ xâu nhị phân khác nhau có độ dài $L$ là dãy con của cả $S$ lẫn $T$.

Đảm bảo rằng trong các giới hạn của bài toán, các xâu như vậy luôn tồn tại.

Dữ liệu vào

Dòng duy nhất của dữ liệu vào chứa một số nguyên $K$ ($1\le K\le 10^9$).

Dữ liệu ra

In các xâu nhị phân không rỗng $S$ và $T$ trên hai dòng riêng biệt. Độ dài của mỗi xâu không được vượt quá $8848$. Chúng có thể có độ dài khác nhau.

Nếu có nhiều hơn một lời giải, bạn có thể in bất kỳ lời giải nào.

Ví dụ

Dữ liệu vào 1

1

Dữ liệu ra 1

1111
00

Dữ liệu vào 2

2

Dữ liệu ra 2

10
01

Dữ liệu vào 3

3

Dữ liệu ra 3

010
1001

Dữ liệu vào 4

100

Dữ liệu ra 4

10001000001011100001010100011
11000010001010101001010011100

Ghi chú

Ở ví dụ thứ nhất, dãy con chung dài nhất của 1111 và 00 có độ dài $0$, và chỉ có một xâu độ dài $0$ là dãy con của cả hai — xâu rỗng.

Ở ví dụ thứ hai, độ dài dãy con chung dài nhất của các xâu 10 và 01 là $1$, và có $2$ xâu độ dài $1$ là dãy con của cả $S$ lẫn $T$: 0 và 1.

Ở ví dụ thứ hai, độ dài dãy con chung dài nhất của các xâu 010 và 1001 là $2$, và có $3$ xâu độ dài $2$ là dãy con của cả $S$ lẫn $T$: 00, 01 và 10.

Tạo ra các xâu dài hơn Everest sẽ là thiếu tôn trọng…