패리티 정렬

길이가 $n$인 순열 $P$가 주어진다. 이 문제에서 순열의 원소는 $0$부터 $n - 1$까지의 정수이다.

$P$를 오름차순으로 정렬하려면 아래 연산을 최대 $30$번 수행한다.

연산은 두 개의 매개변수로 정해진다. 연산의 모드를 나타내는 정수 $t$($0 \le t \le 1$)와 0과 1로만 이루어진 길이 $n$의 문자열 $S$이다.

처음에 비어 있는 수열 $A$와 $B$가 있다.

다음으로 $i$를 $1$부터 $n$까지 바꾸며 아래 단계를 반복한다.

• $S_i = 0$이면 아무것도 하지 않는다.
• $S_i = 1$이면 $P_i$가 짝수일 때 $P_i$를 $A$의 끝에 추가한다. 홀수이면 $B$의 끝에 추가한다.

$t = 0$이면 수열 $C$는 $A$와 $B$를 이 순서로 이어 붙인 것이다.

$t = 1$이면 수열 $C$는 $B$와 $A$를 이 순서로 이어 붙인 것이다.

다음으로 $i$를 $1$부터 $n$까지 바꾸며 아래 단계를 반복한다.

• $S_i = 0$이면 아무것도 하지 않는다.
• $S_i = 1$이면 $P_i$를 $C$의 첫 번째 원소로 바꾸고, 그 원소를 $C$에서 제거한다.

예를 들어 $n = 7$, $P = \{0, 4, 2, 3, 6, 5, 1\}$, $t = 1$, $S = `1101101`$을 택하면 과정은 아래 그림과 같다.

첫 번째 줄에 정수 $n$($1 \le n \le 15\,000$)이 주어진다. 두 번째 줄에는 정수 $P_i$($0 \le P_i \le n - 1$) $n$개가 주어진다. 모든 $P_i$는 서로 다르다.

가능한 정렬 과정 중 하나를 다음 형식으로 출력한다.

첫 줄에 연산 횟수 $k$($0 \le k \le 30$)를 출력한다.

다음 $k$개의 줄에는 $i$번째 연산을 나타내는 정수 $t_i$($0 \le t_i \le 1$)와 길이 $n$인 이진 문자열 $S$를 출력한다.

가능한 답이 여러 개이면 그중 아무거나 출력해도 된다. 연산 횟수를 최소로 만들 필요는 없다.