Chúng ta đều biết rằng $\binom{n}{k} = \frac{n \cdot (n-1) \cdot \dots \cdot (n-k+2) \cdot (n-k+1)}{1 \cdot 2 \cdot \dots \cdot (k-1) \cdot k}$ là một số nguyên với mọi $0 \le k \le n$. Nhưng sẽ thật tuyệt nếu chúng ta có thể chứng minh điều đó bằng cách cung cấp một cặp ghép giữa các thừa số ở tử số và mẫu số, phải không?

Hãy xây dựng một đồ thị hai phía với $k$ đỉnh ở mỗi bên. Đỉnh thứ $i$ ở phần bên trái tương ứng với thừa số $(n + 1 - i)$ từ tử số và đỉnh thứ $j$ ở phần bên phải tương ứng với thừa số $j$ từ mẫu số. Có một cạnh nối $i - j$ nếu và chỉ nếu $j$ chia hết $(n + 1 - i)$. Số $k$ được gọi là "có thể chứng minh" (provable) đối với $n$ nếu tồn tại một cặp ghép hoàn hảo trong đồ thị hai phía này.

Cho $n$, hãy kiểm tra xem $k$ có "có thể chứng minh" hay không với mỗi $k$ thỏa mãn $0 \le k \le n$.

Dữ liệu vào

Dòng duy nhất chứa một số nguyên $n$ ($0 \le n \le 10^{18}$).

Dữ liệu ra

In ra một chuỗi có độ dài $(n + 1)$ bao gồm các ký tự '0' và '1', trong đó ký tự thứ $(k + 1)$ phải là '1' nếu và chỉ nếu $k$ là "có thể chứng minh" đối với $n$.

Bạn nghĩ rằng điều này sẽ dẫn đến lỗi "Output Limit Exceeded"? Hmmm... Được thôi. Hãy nén chuỗi đó lại.

Cho $s_0 = \text{"0"}$ và $s_1 = \text{"1"}$. Bạn có thể định nghĩa $s_2, s_3, \dots, s_t$. Chuỗi $s_i$ phải là sự ghép nối của một vài chuỗi đã được định nghĩa trước đó. Một cách hình thức, $\forall i(2 \le i \le t) : s_i = s_{j_1} + s_{j_2} + \dots + s_{j_{k_i}}$, ở đây $1 \le k_i$, $\forall r(1 \le r \le k_i) : j_r < i$. Chuỗi $s_t$ phải là đáp án của bài toán.

Ở dòng đầu tiên, in ra một số nguyên $t$ ($2 \le t \le 500$).

Trong $t - 1$ dòng tiếp theo, in ra các mô tả của $s_i$. Mỗi mô tả phải có dạng $k_i \ j_1 \ j_2 \ \dots \ j_{k_i}$, với $1 \le k_i$ và $0 \le j_r < i$.

Tổng độ dài của tất cả các mô tả không được vượt quá $10\,000$: $\sum_{i=2}^t k_i \le 10\,000$.

Chúng ta có thể chứng minh rằng với mọi bộ test hợp lệ, luôn tồn tại một cách xây dựng chuỗi đáp án thỏa mãn tất cả các giới hạn trên. Nếu có nhiều cách thực hiện, hãy in ra bất kỳ cách nào trong số đó. Lưu ý rằng bạn không cần phải tối thiểu hóa $t$ hoặc tổng độ dài của tất cả các mô tả.

Ví dụ

Dữ liệu vào 1

1

Dữ liệu ra 1

2
2 1 1

Dữ liệu vào 2

0

Dữ liệu ra 2

2
1 1

Dữ liệu vào 3

7

Dữ liệu ra 3

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

Ghi chú

Trong ví dụ thứ ba: $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"}$.