لدى 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$ في الوقت نفسه.

تنفذ Elsie العمليات دائماً بترتيب الأنواع التصاعدي: العدد الذي تريده (وربما لا شيء) من النوع $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