בהינתן $K$, בנו שתי מחרוזות בינריות לא ריקות $S$ ו-$T$, כל אחת באורך לכל היותר $8848$, כך שיש להן בדיוק $K$ תתי־סדרות משותפות ארוכות ביותר שונות. באופן פורמלי יותר, אם $L$ הוא אורך תת־הסדרה המשותפת הארוכה ביותר של $S$ ו-$T$, צריכות להתקיים בדיוק $K$ מחרוזות בינריות שונות באורך $L$ שהן תתי־סדרות גם של $S$ וגם של $T$.
מובטח שתחת מגבלות הבעיה מחרוזות כאלה תמיד קיימות.
קלט
השורה היחידה של הקלט מכילה מספר שלם אחד $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$, ויש $2$ מחרוזות באורך $1$ שהן תתי־סדרות גם של $S$ וגם של $T$: 0 ו-1.
בדוגמה השנייה, אורך תת־הסדרה המשותפת הארוכה ביותר של המחרוזות 010 ו-1001 הוא $2$, ויש $3$ מחרוזות באורך $2$ שהן תתי־סדרות גם של $S$ וגם של $T$: 00, 01 ו-10.
יהיה זה חוסר כבוד ליצור מחרוזות ארוכות יותר מ-Everest…