คุณได้รับแท่ง $n+1$ แท่งและแผ่นดิสก์ $3n$ แผ่น ในตอนเริ่มต้น แต่ละแท่งใน $n$ แท่งแรกมีแผ่นดิสก์อยู่พอดี 3 แผ่น แผ่นดิสก์แต่ละแผ่นมีสีหนึ่งใน $n$ สี (ระบุด้วยหมายเลขตั้งแต่ $1$ ถึง $n$) นอกจากนี้ แต่ละสีใน $n$ สีมีแผ่นดิสก์พอดี 3 แผ่น แท่งที่ $n+1$ ว่างอยู่

ในแต่ละขั้น เราสามารถเลือกแท่งสองแท่ง $a$ และ $b$ ($a\ne b$) โดยที่ $a$ มีแผ่นดิสก์อย่างน้อย 1 แผ่น และ $b$ มีแผ่นดิสก์ไม่เกิน 2 แผ่น แล้วย้ายแผ่นดิสก์บนสุดจากแท่ง $a$ ไปไว้บนสุดของแท่ง $b$ โปรดทราบว่าในเวลาใดก็ตาม ห้ามมีแท่งใดบรรจุแผ่นดิสก์เกิน 3 แผ่น

เป้าหมายของคุณคือจัดเรียงแผ่นดิสก์ให้เป็นระเบียบ กล่าวให้ชัดเจนคือ คุณต้องดำเนินการจำนวนหนึ่ง (อาจเป็น 0 ครั้ง) เพื่อให้เมื่อสิ้นสุดแล้ว แต่ละแท่งใน $n$ แท่งแรกมีแผ่นดิสก์สีเดียวกันพอดี 3 แผ่น และแท่งที่ $n+1$ ว่างอยู่

จงหาวิธีจัดเรียงแผ่นดิสก์โดยใช้การดำเนินการไม่เกิน $6n$ ครั้ง สามารถพิสูจน์ได้ว่าภายใต้เงื่อนไขนี้ มีคำตอบอยู่เสมอ หากมีหลายคำตอบ จะยอมรับคำตอบใดก็ได้

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มบวก $n$ ($1\le n\le 1000$) อีก 3 บรรทัดถัดมา แต่ละบรรทัดมีจำนวนเต็มบวก $c_{i,j}$ จำนวน $n$ จำนวน ($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$ (ตามที่อธิบายไว้ในโจทย์)

ตัวอย่าง

ข้อมูลนำเข้า 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