E. Хүснэгт шахах

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан Петя одоо өгөгдөл шахалтын алгоритмуудад маш дуртай болсон. Тэр аль хэдийн $gz$, $bz$, $zip$ болон өөр олон алгоритмуудыг судалчихсан. Шинэ мэдлэгтээ урамшсан Петя одоо $dis$ гэж нэрлэхийг хүсэж буй шинэ шахалтын алгоритм хөгжүүлж байгаа.

Петя хүснэгтүүдийг шахахаар шийдсэн. Түүнд эерэг бүхэл тоогоор дүүргэсэн $n$ мөр $m$ баганатай $a$ хүснэгт өгөгдсөн. Тэр мөр болон багана бүрийн харьцангуй дараалал өөрчлөгдөхгүй байх эерэг бүхэл тооноос тогтох $a'$ хүснэгт бүтээхийг хүсч байна. Энэ нь анхны хүснэгтийн $i$-р мөрөнд $a_{i, j} < a_{i, k}$ байсан бол үүсч буй хүснэгтэнд $a'_{i, j} < a'_{i, k}$ байх ба хэрвээ $a_{i, j} = a_{i, k}$ байсан бол $a'_{i, j} = a'_{i, k}$ болно гэсэн үг. Үүнтэй адилаар анхны хүснэгтийн $j$-р багананд $a_{i, j} < a_{p, j}$ байсан бол шахагдсан хүснэгтэнд $a'_{i, j} < a'_{p, j}$ байх ба хэрвээ $a_{i, j} = a_{p, j}$ байсан бол $a'_{i, j} = a'_{p, j}$ болно гэсэн үг.

Том хэмжээний утгуудыг хадгалахад их зай эзлэх учир $a'$-д буй утгын хамгийн их нь аль болох бага байх хэрэгтэй.

Петя онолдоо сайн хэдий ч түүнд алгоритмаа хэрэгжүүлэхэд таны тусламж хэрэгтэй.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $m$ ( байх ба харгалзан хүснэгтийн мөрийн тоо болон баганын тоо юм.

Дараагийн $n$ мөр бүрт $m$ ширхэг бүхэл тоон утгууд $a_{i, j}$ $(1 ≤ a_{i, j} ≤ 10^{9})$ байх ба хүснэгтэнд буй утгууд юм.

Гаралт

Мөр бүрт $m$ бүхэл тоон утга бүхий $n$ мөрөөс тогтох шахагдсан хүснэгтийг хэвлэ.

Хэрвээ шахагдсан хүснэгтэн дах хамгийн их утга боломжит хамгийн бага байх хэд хэдэн хариулт байвал та алийг нь ч хэвлэж болно.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
2 2
1 2
3 4
Гаралт
1 2
2 3
Оролт
4 3
20 10 30
50 40 30
50 60 70
90 80 70
Гаралт
2 1 3
5 4 3
5 6 7
9 8 7

Тэмдэглэл

Эхний жишээн дээр $a_{1, 2} ≠ a_{2, 1}$ байгаа боловч нэг мөр эсвэл нэг баганад байрлаагүй учир шахалтын дараа тэнцүү болж болно.

Сэтгэгдлүүдийг ачааллаж байна...