Vous disposez de $n + 1$ tiges et de $3n$ disques. Initialement, chacune des $n$ premières tiges contient exactement 3 disques. Chacun des disques possède l'une des $n$ couleurs (identifiées par des nombres de 1 à $n$). De plus, il y a exactement 3 disques de chacune des $n$ couleurs. La $(n + 1)$-ième tige est vide.

À chaque étape, nous pouvons sélectionner deux tiges $a$ et $b$ ($a \neq b$) telles que $a$ possède au moins 1 disque et $b$ possède au plus 2 disques, et déplacer le disque supérieur de la tige $a$ vers le sommet de la tige $b$. Notez qu'aucune tige ne peut contenir plus de 3 disques à aucun moment.

Votre objectif est de trier les disques. Plus précisément, vous devez effectuer un certain nombre d'opérations (éventuellement 0), de sorte qu'à la fin, chacune des $n$ premières tiges contienne exactement 3 disques de la même couleur, et que la $(n + 1)$-ième tige soit vide.

Trouvez une solution pour trier les disques en au plus $6n$ opérations. Il peut être prouvé que, sous cette condition, une solution existe toujours. S'il existe plusieurs solutions, n'importe laquelle est acceptée.

Entrée

La première ligne de l'entrée contient un entier positif $n$ ($1 \le n \le 1000$). Les 3 lignes suivantes de l'entrée contiennent $n$ entiers positifs $c_{i,j}$ chacun ($1 \le i \le 3$, $1 \le j \le n$, $1 \le c_{i,j} \le n$), représentant la couleur de chacun des disques initialement placés sur les tiges. La première des 3 lignes indique la rangée supérieure, la deuxième ligne indique la rangée du milieu, et la troisième ligne indique la rangée inférieure.

Sortie

La première ligne de la sortie doit contenir un entier non négatif $k$ ($0 \le k \le 6n$), le nombre d'opérations. Chacune des $k$ lignes suivantes doit contenir deux nombres distincts $a_i, b_i$ ($1 \le a_i, b_i \le n + 1$, pour tout $1 \le i \le k$), représentant la $i$-ième opération (telle que décrite dans l'énoncé).

Exemples

Entrée 1

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

Sortie 1

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

Entrée 2

2
1 2
1 2
1 2

Sortie 2

0