بمعرفة $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$، وتوجد سلسلتان بطول $1$ تكونان تتابعين جزئيين لكل من $S$ و$T$: 0 و1.
في المثال الثاني، طول أطول تتابع جزئي مشترك بين السلسلتين 010 و1001 هو $2$، وتوجد $3$ سلاسل بطول $2$ تكون تتابعات جزئية لكل من $S$ و$T$: 00 و01 و10.
سيكون من قلة الاحترام إنشاء سلاسل أطول من Everest…