$n + 1$개의 막대와 $3n$개의 원반이 주어집니다. 처음에 첫 번째부터 $n$번째까지의 각 막대에는 정확히 3개의 원반이 놓여 있습니다. 각 원반은 $1$부터 $n$까지의 번호로 식별되는 $n$가지 색상 중 하나를 가집니다. 또한, 각 색상의 원반은 정확히 3개씩 존재합니다. $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$번째 연산이 막대 $a_i$에서 막대 $b_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