C. Cyclic Shifts
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

We are given a permutation $$$p$$$ of the integers $$$1$$$ to $$$n$$$.

In a given operation we can choose $$$k \gt 0$$$ indices $$$1 \leq x_1 \lt x_2 \lt \dots \lt x_k \leq n$$$ and cyclic shift the corresponding indices of the permutation one to the right. $$$$$$p_{x_2} := p_{x_1}, p_{x_3} := p_{x_2}, p_{x_4} := p_{x_3}, \dots, p_{x_k} := p_{x_{k-1}}, p_{x_1} := p_{x_k}$$$$$$

Applying this operation for a given $$$k$$$ costs $$$\frac{1}{k}^\star$$$ dollars.

Your goal is to sort the given array using at most 2 dollars.

$$$^\star$$$ For the purposes of the grader, the exact cost will be computed as $$$10^{-8} \left \lceil \frac{10^8}{k} \right \rceil$$$.

Input

The first line of input consists of a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^3$$$).

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2 \dots , p_m$$$ ($$$1\leq p_i \leq n$$$) — the permutation to sort. It is guaranteed that the $$$p_i$$$ will form a permutation.

Output

The first line of output contains a single integer $$$m$$$ — the number of operations you used.

Then follow $$$m$$$ lines of output.

The $$$i+1$$$-st line of output contains a binary string of length $$$n$$$ $$$s_i$$$. If the $$$j$$$-th character of $$$s_i$$$ is $$$1$$$, then $$$j$$$ is an index in the $$$i$$$-th cyclic shift (and the reverse if the $$$j$$$-th character is $$$0$$$).

Each of the $$$m$$$ lines of output must all contain at least one '1'.

Examples
Input
3
2 1 3
Output
4
011
110
111
011
Input
4
1 2 3 4
Output
0