Kita semua tahu bahwa $\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}$ merupakan bilangan bulat untuk setiap $0\le k\le n$. Namun, bukankah menarik jika kita dapat membuktikannya dengan memberikan suatu pencocokan antara faktor-faktor pada pembilang dan penyebut?

Mari membangun graf bipartit dengan $k$ simpul pada setiap bagiannya. Simpul ke-$i$ pada bagian kiri bersesuaian dengan faktor $(n+1-i)$ pada pembilang, dan simpul ke-$j$ pada bagian kanan bersesuaian dengan faktor $j$ pada penyebut. Terdapat sisi $i$ — $j$ jika dan hanya jika $j$ membagi $(n+1-i)$. Bilangan $k$ disebut dapat dibuktikan untuk $n$ jika terdapat pencocokan sempurna pada graf bipartit ini.

Diberikan $n$, periksa apakah $k$ dapat dibuktikan untuk setiap $k$ yang memenuhi $0\le k\le n$.

Masukan

Satu-satunya baris berisi satu bilangan bulat $n$ ($0\le n\le 10^{18}$).

Keluaran

Cetak string sepanjang $(n+1)$ yang terdiri atas 0 dan 1. Karakter ke-$(k+1)$ harus berupa 1 jika dan hanya jika $k$ dapat dibuktikan untuk $n$.

Apa, kamu pikir ini akan menyebabkan Batas Keluaran Terlampaui? Hmmmm... Baiklah. Mari memampatkan string tersebut.

Misalkan $s_0=\text{“0”}$ dan $s_1=\text{“1”}$. Kamu dapat mendefinisikan $s_2,s_3,\ldots,s_t$. String $s_i$ harus merupakan konkatenasi beberapa string yang telah didefinisikan sebelumnya. Secara formal, $\forall i\ (2\le i\le t):s_i=s_{j_1}+s_{j_2}+\ldots+s_{j_{k_i}}$, dengan $1\le k_i$, $\forall r\ (1\le r\le k_i):j_r<i$. String $s_t$ harus merupakan jawaban soal ini.

Pada baris pertama, cetak satu bilangan bulat $t$ ($2\le t\le 500$).

Pada $t-1$ baris berikutnya, cetak deskripsi $s_i$. Setiap deskripsi harus berbentuk $k_i\ j_1\ j_2\ \ldots\ j_{k_i}$, dengan $1\le k_i$ dan $0\le j_r<i$.

Panjang total semua deskripsi tidak boleh melebihi $10\,000$: $\sum_{i=2}^{t}k_i\le 10\,000$.

Dapat ditunjukkan bahwa untuk setiap pengujian yang valid, selalu ada cara membangun string jawaban yang memenuhi semua batasan. Jika terdapat beberapa cara, cetak salah satunya. Perhatikan bahwa kamu tidak perlu meminimalkan $t$ ataupun panjang total semua deskripsi.

Contoh

Masukan 1

1

Keluaran 1

2
2 1 1

Masukan 2

0

Keluaran 2

2
1 1

Masukan 3

7

Keluaran 3

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

Catatan

Pada contoh ketiga: $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”}$.