Вам дано $n+1$ стрижнів і $3n$ дисків. Спочатку кожен із перших $n$ стрижнів містить рівно 3 диски. Кожен диск має один із $n$ кольорів (позначених числами від $1$ до $n$). Крім того, є рівно 3 диски кожного з $n$ кольорів. $(n+1)$-й стрижень порожній.

На кожному кроці можна обрати два стрижні $a$ та $b$ ($a \ne b$), такі що на $a$ є щонайменше 1 диск, а на $b$ — щонайбільше 2 диски, і перемістити верхній диск зі стрижня $a$ на вершину стрижня $b$. Зауважте, що в жодний момент на жодному стрижні не може бути більше ніж 3 диски.

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

Знайдіть спосіб відсортувати диски щонайбільше за $6n$ операцій. Можна довести, що за цієї умови розв'язок завжди існує. Якщо є кілька розв'язків, приймається будь-який.

Вхідні дані

Перший рядок вхідних даних містить додатне ціле число $n$ ($1 \le n \le 1\,000$). Наступні 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