Otrzymujesz $n + 1$ prętów i $3n$ dysków. Początkowo każdy z pierwszych $n$ prętów zawiera dokładnie 3 dyski. Każdy z dysków ma jeden z $n$ kolorów (oznaczonych liczbami od 1 do $n$). Ponadto, dla każdego z $n$ kolorów istnieją dokładnie 3 dyski. Pręt o numerze $n + 1$ jest pusty.

W każdym kroku możemy wybrać dwa pręty $a$ oraz $b$ ($a \neq b$) takie, że pręt $a$ zawiera co najmniej 1 dysk, a pręt $b$ zawiera co najwyżej 2 dyski, i przenieść najwyższy dysk z pręta $a$ na szczyt pręta $b$. Zauważ, że żaden pręt nie może w żadnym momencie zawierać więcej niż 3 dyski.

Twoim celem jest posortowanie dysków. Mówiąc dokładniej, musisz wykonać pewną liczbę operacji (być może zero), tak aby na końcu każdy z pierwszych $n$ prętów zawierał dokładnie 3 dyski tego samego koloru, a pręt $n + 1$ był pusty.

Znajdź rozwiązanie sortujące dyski w co najwyżej $6n$ operacjach. Można udowodnić, że przy tym założeniu rozwiązanie zawsze istnieje. Jeśli istnieje wiele rozwiązań, każde z nich jest akceptowalne.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą dodatnią $n$ ($1 \le n \le 1000$). Kolejne 3 linie wejścia zawierają po $n$ liczb całkowitych dodatnich $c_{i,j}$ ($1 \le i \le 3, 1 \le j \le n, 1 \le c_{i,j} \le n$), określających kolor każdego z dysków umieszczonych początkowo na prętach. Pierwsza z 3 linii wskazuje górny rząd, druga linia wskazuje środkowy rząd, a trzecia linia wskazuje dolny rząd.

Wyjście

Pierwsza linia wyjścia musi zawierać nieujemną liczbę całkowitą $k$ ($0 \le k \le 6n$), liczbę operacji. Każda z kolejnych $k$ linii powinna zawierać dwie różne liczby $a_i, b_i$ ($1 \le a_i, b_i \le n + 1$, dla wszystkich $1 \le i \le k$), reprezentujące $i$-tą operację (zgodnie z opisem w treści zadania).

Przykład

Wejście 1

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

Wyjście 1

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

Wejście 2

2
1 2
1 2
1 2

Wyjście 2

0