נתונים $n+1$ מוטות ו־$3n$ דיסקיות. בתחילה, כל אחד מ־$n$ המוטות הראשונים מכיל בדיוק 3 דיסקיות. כל דיסקית היא באחד מ־$n$ צבעים (המזוהים במספרים מ־$1$ עד $n$). נוסף על כך, יש בדיוק 3 דיסקיות מכל אחד מ־$n$ הצבעים. המוט ה־$(n+1)$ ריק.

בכל צעד אפשר לבחור שני מוטות $a$ ו־$b$ ‏($a \ne b$), כך שעל $a$ יש לפחות דיסקית אחת ועל $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$ (כמתואר בתיאור הבעיה).

דוגמאות

קלט 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