# SEERC 2021

# Disk Sort

You are given **n** + **1** rods and **3n** disks. Initially, each of the first **n** rods contains exactly **3** disks. Each of the disks has one of **n** colors (identified by numbers from **1** to **n**). Moreover, there are exactly **3** disks of each of the **n** colors. The (**n** + **1**)-th rod is empty.

At each step we can select two rods **a** and **b** (**a** ≠ **b**) such that **a** has at least **1** disk and **b** has at most **2** disks, and move the topmost disk from rod **a** to the top of rod **b**. Note that no rod is allowed to contain more than **3** disks at any time.

Your goal is to sort the disks. More specifically, you have to do a number of operations (potentially **0**), so that, at the end, each of the first **n** rods contains exactly **3** disks of the same color, and the (**n** + **1**)-th rod is empty.

Find out a solution to sort the disks in at most **6n** operations. It can be proven that, under this condition, a solution always exists. If there are multiple solutions, any one is accepted.

#### Input

The first line contains a positive integer **n** (**1** ≤ **n** ≤ **1000**). The next **3** lines contain **n** positive integers `c`

each (_{i,j}**1** ≤ **i** ≤ **3**, **1** ≤ **j** ≤ **n**, **1** ≤ `c`

≤ _{i,j}**n**), the color each of the disks initially placed on the rods. The first of the **3** lines indicates the upper row, the second line indicates the middle row, and the third line indicates the lower row.

#### Output

The first line must contain a non-negative integer **k** (**0** ≤ **k** ≤ **6n**), the number of operations. Each of the following **k** lines should contain two distinct numbers `a`

, _{i}`b`

(_{i}**1** ≤ `a`

, _{i}`b`

≤ _{i}**n** + **1**, for all **1** ≤ **i** ≤ **k**), representing the **i**-th operation (as described in the statement).

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

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

2 1 2 1 2 1 2

0