Wszyscy wiemy, że $\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}$ jest liczbą całkowitą dla dowolnego $0 \le k \le n$. Byłoby jednak miło, gdybyśmy mogli to udowodnić poprzez wskazanie dopasowania między czynnikami w liczniku i mianowniku, prawda?

Zbudujmy graf dwudzielny z $k$ wierzchołkami w każdej części. $i$-ty wierzchołek w lewej części odpowiada czynnikowi $(n + 1 - i)$ z licznika, a $j$-ty wierzchołek w prawej części odpowiada czynnikowi $j$ z mianownika. Krawędź $i - j$ istnieje wtedy i tylko wtedy, gdy $j$ dzieli $(n + 1 - i)$. Liczba $k$ jest dowodliwa dla $n$, jeśli w tym grafie dwudzielnym istnieje skojarzenie doskonałe.

Dla danego $n$ sprawdź, czy $k$ jest dowodliwe dla każdego $k$ spełniającego $0 \le k \le n$.

Wejście

Jedyna linia zawiera jedną liczbę całkowitą $n$ ($0 \le n \le 10^{18}$).

Wyjście

Wypisz ciąg o długości $(n + 1)$ składający się z znaków '0' i '1', gdzie $(k + 1)$-szy znak powinien być równy '1' wtedy i tylko wtedy, gdy $k$ jest dowodliwe dla $n$.

Myślisz, że to spowoduje przekroczenie limitu wyjścia (Output Limit Exceeded)? Hmm... Dobrze. Skompresujmy ten ciąg.

Niech $s_0 = \text{"0"}$ oraz $s_1 = \text{"1"}$. Możesz zdefiniować $s_2, s_3, \dots, s_t$. Ciąg $s_i$ powinien być konkatenacją kilku wcześniej zdefiniowanych ciągów. Formalnie, $\forall i (2 \le i \le t) : s_i = s_{j_1} + s_{j_2} + \dots + s_{j_{k_i}}$, gdzie $1 \le k_i$ oraz $\forall r (1 \le r \le k_i) : j_r < i$.

Ciąg $s_t$ powinien być odpowiedzią do zadania.

W pierwszej linii wypisz jedną liczbę całkowitą $t$ ($2 \le t \le 500$).

W kolejnych $t - 1$ liniach wypisz opisy $s_i$. Każdy opis powinien mieć postać $k_i \ j_1 \ j_2 \ \dots \ j_{k_i}$, gdzie $1 \le k_i$ oraz $0 \le j_r < i$.

Całkowita długość wszystkich opisów nie powinna przekraczać $10\,000$: $\sum_{i=2}^t k_i \le 10\,000$.

Możemy wykazać, że dla wszystkich poprawnych testów istnieje sposób na skonstruowanie ciągu odpowiedzi spełniającego wszystkie ograniczenia. Jeśli istnieje kilka możliwych sposobów, wypisz dowolny z nich. Zauważ, że nie musisz minimalizować $t$ ani całkowitej długości wszystkich opisów.

Przykład

Wejście 1

1

Wyjście 1

2
2 1 1

Wejście 2

0

Wyjście 2

2
1 1

Wejście 3

7

Wyjście 3

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

Uwagi

W trzecim przykładzie: $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"}$.