نعلم جميعًا أن $\binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+2) \cdot (n-k+1)}{1 \cdot 2 \cdots (k-1) \cdot k}$ عدد صحيح لكل $0 \le k \le n$. لكن ألن يكون جميلًا أن نثبت ذلك بتقديم مطابقة بين عوامل البسط وعوامل المقام؟

لنبنِ رسمًا بيانيًا ثنائي القسم، في كل قسم منه $k$ رأسًا. يقابل الرأس رقم $i$ في القسم الأيسر العامل $n+1-i$ من البسط، ويقابل الرأس رقم $j$ في القسم الأيمن العامل $j$ من المقام. توجد حافة بين $i$ و$j$ إذا وفقط إذا كان $j$ يقسم $n+1-i$. يكون العدد $k$ قابلًا للإثبات بالنسبة إلى $n$ إذا وُجدت مطابقة كاملة في هذا الرسم الثنائي.

عند إعطاء $n$، تحقق مما إذا كان $k$ قابلًا للإثبات لكل $k$ يحقق $0 \le k \le n$.

الإدخال

يحتوي السطر الوحيد على عدد صحيح واحد $n$، حيث $0 \le n \le 10^{18}$.

الإخراج

اطبع سلسلة طولها $n+1$ مكونة من 0 و1، بحيث يكون المحرف رقم $k+1$ هو 1 إذا وفقط إذا كان $k$ قابلًا للإثبات بالنسبة إلى $n$.

ماذا، أتظن أن ذلك سيتجاوز حد حجم الإخراج؟ هممم... حسنًا، لنضغط السلسلة.

لتكن $s_0 = \text{“0”}$ و$s_1 = \text{“1”}$. يمكنك تعريف $s_2, s_3, \ldots, s_t$. يجب أن تكون السلسلة $s_i$ وصلًا لعدة سلاسل عُرّفت سابقًا. بصورة رسمية، لكل $i$ يحقق $2 \le i \le t$، يكون $s_i = s_{j_1} + s_{j_2} + \cdots + s_{j_{k_i}}$، حيث $1 \le k_i$، ولكل $r$ يحقق $1 \le r \le k_i$ يكون $j_r < i$. يجب أن تكون السلسلة $s_t$ إجابة المسألة.

اطبع في السطر الأول عددًا صحيحًا واحدًا $t$، حيث $2 \le t \le 500$.

اطبع في الأسطر $t-1$ التالية أوصاف $s_i$. يجب أن يكون كل وصف بالشكل $k_i\ j_1\ j_2\ \ldots\ j_{k_i}$، حيث $1 \le k_i$ و$0 \le j_r < i$.

يجب ألا يتجاوز الطول الإجمالي لجميع الأوصاف $10\,000$، أي $\sum_{i=2}^{t} k_i \le 10\,000$.

يمكننا إثبات وجود طريقة لبناء سلسلة الإجابة ضمن جميع القيود لكل اختبار صالح. إذا وُجدت عدة طرق، فاطبع أيًا منها. لاحظ أنك لست مطالبًا بتصغير $t$ أو الطول الإجمالي لجميع الأوصاف.

أمثلة

الإدخال 1

1

الإخراج 1

2
2 1 1

الإدخال 2

0

الإخراج 2

2
1 1

الإدخال 3

7

الإخراج 3

4
2 1 1
4 1 2 0 0
3 3 1 2

ملاحظة

في المثال الثالث: $s_2 = s_1+s_1 = \text{“1”}+\text{“1”}=\text{“11”}$، و$s_3 = s_1+s_2+s_0+s_0 = \text{“1”}+\text{“11”}+\text{“0”}+\text{“0”}=\text{“11100”}$، و$s_4 = s_3+s_1+s_2 = \text{“11100”}+\text{“1”}+\text{“11”}=\text{“11100111”}$.