У вас есть $n + 1$ стержень и $3n$ дисков. Изначально каждый из первых $n$ стержней содержит ровно 3 диска. Каждый диск имеет один из $n$ цветов (обозначенных числами от 1 до $n$). Более того, имеется ровно 3 диска каждого из $n$ цветов. $(n + 1)$-й стержень пуст.

На каждом шаге можно выбрать два стержня $a$ и $b$ ($a \neq b$) таких, что на стержне $a$ есть хотя бы 1 диск, а на стержне $b$ не более 2 дисков, и переместить верхний диск со стержня $a$ на вершину стержня $b$. Заметьте, что ни один стержень не может содержать более 3 дисков в любой момент времени.

Ваша цель — отсортировать диски. А именно, необходимо выполнить некоторое количество операций (возможно, 0) так, чтобы в конце каждый из первых $n$ стержней содержал ровно 3 диска одного цвета, а $(n + 1)$-й стержень был пустым.

Найдите решение для сортировки дисков не более чем за $6n$ операций. Можно доказать, что при таком условии решение всегда существует. Если существует несколько решений, допускается любое из них.

Входные данные

Первая строка входных данных содержит целое положительное число $n$ ($1 \le n \le 1000$). Следующие 3 строки содержат по $n$ целых положительных чисел $c_{i,j}$ ($1 \le i \le 3, 1 \le j \le n, 1 \le c_{i,j} \le n$), обозначающих цвет каждого из дисков, изначально расположенных на стержнях. Первая из 3 строк указывает верхний ряд, вторая строка — средний ряд, а третья строка — нижний ряд.

Выходные данные

Первая строка выходных данных должна содержать неотрицательное целое число $k$ ($0 \le k \le 6n$), количество операций. Каждая из следующих $k$ строк должна содержать два различных числа $a_i, b_i$ ($1 \le a_i, b_i \le n + 1$ для всех $1 \le i \le k$), представляющих $i$-ю операцию (как описано в условии).

Примеры

Входные данные 1

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

Выходные данные 1

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

Входные данные 2

2
1 2
1 2
1 2

Выходные данные 2

0