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$$$.
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.
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'.
3 2 1 3
4 011 110 111 011
4 1 2 3 4
0
| Name |
|---|


