כולנו יודעים ש-$\binom{n}{k}=\frac{n\cdot(n-1)\cdot\ldots\cdot(n-k+2)\cdot(n-k+1)}{1\cdot2\cdot\ldots\cdot(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=$"0" ו-$s_1=$"1". אתם יכולים להגדיר את $s_2,s_3,\ldots,s_t$. המחרוזת $s_i$ צריכה להיות שרשור של כמה מחרוזות שהוגדרו קודם. באופן פורמלי, $\forall i\ (2 \le i \le t): s_i=s_{j_1}+s_{j_2}+\ldots+s_{j_{k_i}}$, כאשר $1 \le k_i$, $\forall 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”}$.