Bạn được cho $n + 1$ cọc và $3n$ đĩa. Ban đầu, mỗi cọc trong số $n$ cọc đầu tiên chứa đúng 3 đĩa. Mỗi đĩa có một trong $n$ màu (được xác định bằng các số từ 1 đến $n$). Hơn nữa, có đúng 3 đĩa của mỗi màu trong số $n$ màu. Cọc thứ $n + 1$ đang trống.

Tại mỗi bước, bạn có thể chọn hai cọc $a$ và $b$ ($a \neq b$) sao cho cọc $a$ có ít nhất 1 đĩa và cọc $b$ có tối đa 2 đĩa, sau đó di chuyển đĩa trên cùng từ cọc $a$ sang đỉnh của cọc $b$. Lưu ý rằng không cọc nào được phép chứa quá 3 đĩa tại bất kỳ thời điểm nào.

Mục tiêu của bạn là sắp xếp các đĩa. Cụ thể hơn, bạn cần thực hiện một số thao tác (có thể là 0), sao cho cuối cùng, mỗi cọc trong số $n$ cọc đầu tiên chứa đúng 3 đĩa cùng màu, và cọc thứ $n + 1$ trống.

Hãy tìm một giải pháp để sắp xếp các đĩa trong tối đa $6n$ thao tác. Có thể chứng minh rằng với điều kiện này, một giải pháp luôn tồn tại. Nếu có nhiều giải pháp, bất kỳ giải pháp nào cũng được chấp nhận.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên dương $n$ ($1 \le n \le 1000$). 3 dòng tiếp theo của dữ liệu vào chứa $n$ số nguyên dương $c_{i,j}$ mỗi dòng ($1 \le i \le 3, 1 \le j \le n, 1 \le c_{i,j} \le n$), là màu của các đĩa được đặt trên các cọc ban đầu. Dòng đầu tiên trong 3 dòng biểu thị hàng trên cùng, dòng thứ hai biểu thị hàng giữa và dòng thứ ba biểu thị hàng dưới cùng.

Dữ liệu ra

Dòng đầu tiên của dữ liệu ra phải chứa một số nguyên không âm $k$ ($0 \le k \le 6n$), là số lượng thao tác. Mỗi dòng trong số $k$ dòng tiếp theo phải chứa hai số phân biệt $a_i, b_i$ ($1 \le a_i, b_i \le n + 1$, với mọi $1 \le i \le k$), biểu thị thao tác thứ $i$ (như đã mô tả trong đề bài).

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

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

Dữ liệu vào 2

2
1 2
1 2
1 2

Dữ liệu ra 2

0