เราทุกคนรู้ว่า $\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=\text{“0”}$ และ $s_1=\text{“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”}$