São dadas $n + 1$ hastes e $3n$ discos. Inicialmente, cada uma das primeiras $n$ hastes contém exatamente $3$ discos. Cada disco tem uma de $n$ cores (identificadas por números de $1$ a $n$). Além disso, há exatamente $3$ discos de cada uma das $n$ cores. A $(n + 1)$-ésima haste está vazia.

Em cada passo, podemos escolher duas hastes $a$ e $b$ ($a \ne b$), de modo que $a$ tenha pelo menos $1$ disco e $b$ tenha no máximo $2$ discos, e mover o disco do topo da haste $a$ para o topo da haste $b$. Observe que nenhuma haste pode conter mais de $3$ discos em momento algum.

O seu objetivo é ordenar os discos. Mais especificamente, deve realizar um certo número de operações (possivelmente $0$) para que, no final, cada uma das primeiras $n$ hastes contenha exatamente $3$ discos da mesma cor, e a $(n + 1)$-ésima haste esteja vazia.

Encontre uma solução para ordenar os discos com, no máximo, $6n$ operações. Pode provar-se que, sob essa condição, existe sempre uma solução. Se houver várias soluções, qualquer uma será aceite.

Entrada

A primeira linha da entrada contém um inteiro positivo $n$ ($1 \le n \le 1\,000$). Cada uma das 3 linhas seguintes contém $n$ inteiros positivos $c_{i,j}$ ($1 \le i \le 3$, $1 \le j \le n$, $1 \le c_{i,j} \le n$), as cores dos discos inicialmente colocados nas hastes. A primeira dessas 3 linhas indica a fila superior, a segunda indica a fila do meio e a terceira indica a fila inferior.

Saída

A primeira linha da saída deve conter um inteiro não negativo $k$ ($0 \le k \le 6n$), o número de operações. Cada uma das $k$ linhas seguintes deve conter dois números distintos $a_i, b_i$ ($1 \le a_i, b_i \le n + 1$, para todo $1 \le i \le k$), representando a $i$-ésima operação (conforme descrita no enunciado).

Exemplos

Entrada 1

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

Saída 1

8
3 5
3 5
2 3
2 5
2 3
5 2
5 2
5 2

Entrada 2

2
1 2
1 2
1 2

Saída 2

0