ל־Bessie יש טבלת חיבור $N\times N$ ($1\le N\le 1000$), שבה המספר בשורה $r$ ובעמודה $c$ הוא $r+c$ לכל $1\le r,c\le N$. למשל, כש־$N=3$:

2 3 4
3 4 5
4 5 6

לרוע המזל Elsie לקחה את הטבלה ושינתה אותה באמצעות ביצוע שלוש הפעולות הבאות כמה פעמים שרצתה.

1. להחליף שתי שורות

2. להחליף שתי עמודות

3. לבחור ערכים $a$ ו־$b$ שקיימים בטבלה ולהחליף בו זמנית כל $a$ ב־$b$ וכל $b$ ב־$a$.

הסוגים תמיד מבוצעים בסדר עולה: כמה פעולות שרוצים (אולי אף אחת) מסוג $1$, אחר כך מסוג $2$, ולבסוף מסוג $3$.

שחזרו מצב אפשרי אחרי כל הפעולות מסוג $1$ ו־$2$, אבל לפני כל פעולה מסוג $3$. אם יש כמה תשובות, הדפיסו את הקטנה ביותר לקסיקוגרפית.

להשוואת טבלאות לקסיקוגרפית, קראו בסדר הטבעי (שורות מלמעלה למטה, משמאל לימין בכל שורה) והשוו את הערכים השונים הראשונים.

קלט

השורה הראשונה מכילה $N$.

כל אחת מ־$N$ השורות הבאות מכילה $N$ שלמים, טבלת החיבור אחרי השינויים של Elsie.

פלט

הדפיסו את המצב האפשרי המזערי לקסיקוגרפית אחרי כל הפעולות מסוגים 1 ו־2, אבל לפני סוג 3. תשובה קיימת בוודאות.

דוגמאות

קלט 1

1
2

פלט 1

2

הערה

בלי קשר לפעולות של Elsie, הטבלה אינה משתנה.

קלט 2

3
3 4 2
5 2 3
6 3 5

פלט 2

4 2 3
5 3 4
6 4 5

הערה

הנה רצף פעולות אפשרי שלה.

2 3 4
3 4 5
4 5 6
-> (פעולה 1: להחליף עמודות 2 ו־3)
2 4 3
3 5 4
4 6 5
-> (פעולה 1: להחליף עמודות 1 ו־2)
4 2 3
5 3 4
6 4 5
-> (פעולה 3: להחליף ערכים 2 ו־3)
4 3 2
5 2 4
6 4 5
-> (פעולה 3: להחליף ערכים 3 ו־4)
3 4 2
5 2 3
6 3 5

הערה: גם המצב הבא אפשרי אחרי סוגים 1 ו־2, אבל אינו מזערי לקסיקוגרפית כי הערך השני בשורה הראשונה גדול מזה שבתשובה הנכונה.

4 6 5
3 5 4
2 4 3

קלט 3

6
8 10 5 6 7 4
12 11 10 4 8 2
5 4 6 7 9 8
10 2 4 8 5 12
6 8 7 9 3 5
4 12 8 5 6 10

פלט 3

7 5 8 9 10 6
4 2 5 6 7 3
8 6 9 10 11 7
5 3 6 7 8 4
9 7 10 11 12 8
6 4 7 8 9 5

תת־משימות

• קלטים 4-5: $N\le 6$
• קלטים 6-7: $N\le 8$
• קלטים 8-11: $N\le 100$
• קלטים 12-15: אין מגבלות נוספות.

מחבר הבעיה: Benjamin Qi