Бяцхан Петя одоо өгөгдөл шахалтын алгоритмуудад маш дуртай болсон. Тэр аль хэдийн $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$ мөрөөс тогтох шахагдсан хүснэгтийг хэвлэ.

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

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