I: 偶奇ソート

問題文

$0$ から $N-1$ までの整数を並び替えた長さ $N$ の順列 $P$ が与えられます。

以下の操作を最大 $30$ 回まで行って、 $P$ を昇順に並べ替えてください。

操作

$1$ 回の操作では、次の 1 から 4 を順に行う。

  1. 0 と 1 からなる長さ $N$ の文字列 $S$ と、整数 $t$ ( $t = 0$ または $t = 1$ ) を宣言する。
  2. 空の数列 $A, B$ を用意し、整数 $i$ を $1$ から $N$ まで動かしながら以下を行う。
    • $S_i$ が 0 のとき、何もしない。
    • $S_i$ が 1 のとき、
      • $P_i$ が偶数ならば $A$ の末尾に $P_i$ を追加する。
      • $P_i$ が奇数ならば $B$ の末尾に $P_i$ を追加する。
  3. 数列 $C$ を以下のように定義する。
    • $t = 0$ のとき、 $C$ は $A$ と $B$ をこの順に連結したものとする。
    • $t = 1$ のとき、 $C$ は $B$ と $A$ をこの順に連結したものとする。
  4. 整数 $i$ を $1$ から $N$ まで動かしながら以下を行う。
    • $S_i$ が 0 のとき、何もしない。
    • $S_i$ が 1 のとき、 $P_i$ ã‚’ $C$ の先頭の要素に置き換え、 $C$ の先頭の要素を消す。

例えば、$N = 7, P = {0, 4, 2, 3, 6, 5, 1}$ とします。

$S$ を "1101101" とし、$t = 1$ とした操作を $1$ 回行うと、以下の図のように $P = {3, 1, 2, 0, 4, 5, 6}$ となります。

parity-sort-example

制約

  • $1 \leq N \leq 15000$
  • $P$ は $0$ から $N-1$ までの整数を並び替えた順列

入力

入力は以下の形式で標準入力から与えられる。

$N$
$P_1$ $P_2$ $\ldots$ $P_N$

出力

$30$ 回以内の操作で $P$ を昇順に並べ替えるような操作列の $1$ つを以下の形式で出力せよ。このような操作列は複数存在するかもしれないが、どれを出力しても正答となる。

  • $1$ 行目には、操作を行う回数 $K$ を出力せよ。ただし、 $0 \le K \le 30$ でなければならない。
  • $i + 1$ 行目 $(1 \le i \le K)$ には、 $i$ 回目の操作で宣言する整数 $t_i (t_i = 0,1)$ および長さ $N$ の文字列 $S_i$ をこの順に出力せよ。
$K$
$t_1$ $S_1$
$t_2$ $S_2$
$\vdots$
$t_K$ $S_K$

入力例1

7
0 4 2 3 6 5 1

出力例1

1
1 0100101

操作を行うと、$A = { 4, 6 }, B = { 1 }$ となり、 $t = 1$ より $C = { 1, 4, 6 }$ となります。

$P$ の要素を $C$ によって置き換えると、 $P = { 0, 1, 2, 3, 4, 5, 6 }$ となるので、この操作で $P$ を昇順に並べ替えることができます。

入力例2

4
1 0 3 2

出力例2

2
0 1100
0 0011

例えば以下のような出力も正答となります。

2
0 1111
1 0110

入力例3

1
0

出力例3

0

操作を行わなくても構いません。