私たちは皆、$\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}$ が任意の $0 \le k \le n$ に対して整数であることを知っています。しかし、分子と分母の因子の間にマッチングを与えることでこれを証明できたら素晴らしいと思いませんか？

左側に $k$ 個、右側に $k$ 個の頂点を持つ二部グラフを構築しましょう。左側の $i$ 番目の頂点は分子の因子 $(n + 1 - i)$ に対応し、右側の $j$ 番目の頂点は分母の因子 $j$ に対応します。$j$ が $(n + 1 - i)$ を割り切る場合に限り、頂点 $i$ と $j$ の間に辺が存在するとします。この二部グラフに完全マッチングが存在する場合、数 $k$ は $n$ に対して「証明可能」であると言います。

$n$ が与えられたとき、$0 \le k \le n$ を満たす各 $k$ について、$k$ が証明可能かどうかを判定してください。

入力

入力は1行のみで、整数 $n$ ($0 \le n \le 10^{18}$) が与えられます。

出力

長さ $(n + 1)$ の '0' と '1' からなる文字列を出力してください。$(k + 1)$ 番目の文字は、$k$ が $n$ に対して証明可能である場合に限り '1' とします。

これでは出力制限を超えてしまうと思うでしょうか？うーん……わかりました。文字列を圧縮しましょう。

$s_0 = \text{“0”}$、$s_1 = \text{“1”}$ とします。$s_2, s_3, \dots, s_t$ を定義できます。文字列 $s_i$ は、それ以前に定義されたいくつかの文字列の連結である必要があります。形式的には、$\forall i(2 \le i \le t) : s_i = s_{j_1} + s_{j_2} + \dots + s_{j_{k_i}}$ であり、ここで $1 \le k_i$ かつ $\forall r(1 \le r \le k_i) : j_r < i$ です。文字列 $s_t$ が問題の答えとなる必要があります。

1行目に整数 $t$ ($2 \le t \le 500$) を出力してください。 続く $t - 1$ 行に $s_i$ の記述を出力してください。各記述は $k_i \ j_1 \ j_2 \ \dots \ 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

2
2 1 1

入出力例 2

0

2
1 1

入出力例 3

7

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

注記

3番目の例において：$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”}$ となります。