$n + 1$ 本の棒と $3n$ 個の円盤が与えられます。最初、最初の $n$ 本の棒にはそれぞれちょうど 3 個の円盤が置かれています。各円盤は $n$ 色のうちのいずれか（1 から $n$ までの番号で識別されます）で塗られています。さらに、各色の円盤はちょうど 3 個ずつ存在します。$n + 1$ 番目の棒は空です。

各ステップで、2 本の棒 $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$) が含まれます。3 行のうち最初の行は上段、2 行目は中段、3 行目は下段を表します。

出力

出力の最初の行には、操作回数を表す非負の整数 $k$ ($0 \le k \le 6n$) を出力してください。続く $k$ 行のそれぞれには、2 つの異なる数字 $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