กำหนด $K$ ให้ จงสร้างสตริงฐานสองที่ไม่ว่าง $S$ และ $T$ ซึ่งแต่ละสตริงมีความยาวไม่เกิน $8848$ และมีลำดับย่อยร่วมที่ยาวที่สุดแตกต่างกันพอดี $K$ แบบ กล่าวอย่างเป็นทางการ หาก $L$ คือความยาวของลำดับย่อยร่วมที่ยาวที่สุดของ $S$ และ $T$ จะต้องมีสตริงฐานสองที่แตกต่างกันซึ่งมีความยาว $L$ และเป็นลำดับย่อยของทั้ง $S$ และ $T$ พอดี $K$ สตริง

รับประกันว่าภายใต้ข้อจำกัดของโจทย์นี้จะมีสตริงเช่นนั้นอยู่เสมอ

ข้อมูลนำเข้า

ข้อมูลนำเข้ามีบรรทัดเดียวซึ่งมีจำนวนเต็ม $K$ ($1\le K\le 10^9$)

ข้อมูลส่งออก

พิมพ์สตริงฐานสองที่ไม่ว่าง $S$ และ $T$ แยกกันคนละบรรทัด ความยาวของแต่ละสตริงต้องไม่เกิน $8848$ ทั้งสองสตริงมีความยาวต่างกันได้

หากมีคำตอบมากกว่าหนึ่งคำตอบ สามารถพิมพ์คำตอบใดก็ได้

ตัวอย่าง

ข้อมูลนำเข้า 1

1

ข้อมูลส่งออก 1

1111
00

ข้อมูลนำเข้า 2

2

ข้อมูลส่งออก 2

10
01

ข้อมูลนำเข้า 3

3

ข้อมูลส่งออก 3

010
1001

ข้อมูลนำเข้า 4

100

ข้อมูลส่งออก 4

10001000001011100001010100011
11000010001010101001010011100

หมายเหตุ

ในตัวอย่างแรก ลำดับย่อยร่วมที่ยาวที่สุดของ 1111 และ 00 มีความยาว $0$ และมีสตริงความยาว $0$ เพียงสตริงเดียวที่เป็นลำดับย่อยของทั้งสองสตริง นั่นคือสตริงว่าง

ในตัวอย่างที่สอง ความยาวของลำดับย่อยร่วมที่ยาวที่สุดของสตริง 10 และ 01 คือ $1$ และมีสตริงความยาว $1$ ที่เป็นลำดับย่อยของทั้ง $S$ และ $T$ อยู่ $2$ สตริง ได้แก่ 0 และ 1

ในตัวอย่างที่สอง ความยาวของลำดับย่อยร่วมที่ยาวที่สุดของสตริง 010 และ 1001 คือ $2$ และมีสตริงความยาว $2$ ที่เป็นลำดับย่อยของทั้ง $S$ และ $T$ อยู่ $3$ สตริง ได้แก่ 00, 01 และ 10

การสร้างสตริงที่ยาวกว่า Everest คงเป็นการไม่ให้เกียรติ…