D. Гайхалтай матриц

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

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

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

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

Леннид эерэг бүхэл тоон $n × m$ матриц байв. Тус матрицын мөр тус бүр нь өсөх дарааллаар байрласан учир энэхүү матриц түүнд ихэд таалагджээ. Ийм шалтгаанаар тэрээр бүхэл тоон матрицыг гайхалтай матриц гэж нэрлэнэ.

Нэгэн өдөр Ленниг сургууль дээрээ байхад түүний дүү өрөөнд нь матрицаар нь тоглож байлаа. Тэрээр матрицын хэд хэдэн нүдний утгыг арилган, зарим багануудынх нь дарааллыг өөрчилчихсөн байв. Ленни гэртээ ирж үүнийг хараад ихэд гуниглав. Одоо Ленни матрицаа сэргээж анхны байдалд нь оруулахыг хүсч байна.

Түүнд матрицын багануудын дарааллыг олоход тусална уу. Ийнхүү матрицын багануудын дарааллыг олсноор арилгасан нүдний утгыг олж бөглөн дахин гайхалтай матриц бий болгох боломжтой юм. Матрицын арилгасан нүдийг дурын тоогоор бөглөж болохыг анхаарна уу.

Оролт

Эхний мөрөнд $n$ болон $m$ ($1 ≤ n \cdot m ≤ 10^{5}$) гэсэн хоёр бүхэл тоо агуулагдана. Дараагийн $n$ мөрүүд тус бүр нь матрицыг харуулсан өөр хоорондоо зайгаар тусгаарлагдсан $m$ тооны бүхэл тоо агуулна. "-1" нь матрицын арилгагдсан нүдний утгыг илтгэнэ. Бусад бүх бүхэл тоонууд нь ($0$-ээс $10^{9}$ хүртэл) матрицын нүдний утгыг илэрхийлнэ.

Гаралт

Хэрэв багануудын байрлалыг дахин сэргээх боложгүй бол "-1" гэж хэвлэнэ үү. Хэрэв боломжтой бол багануудыг сэлгэж байрлуулсан өөрчлөлтийг илэрхийлэх $p_{1}, p_{2}, ..., p_{m}$ гэсэн $m$ ширхэг бүхэл тоо хэвлэнэ үү.

Энэ нь гайхалтай матрицын $1$ дэхь багана оролтонд өгөгдсөн матрицын $p_1$-р баганаас, $2$ дахь нь багана оролтонд өгөгдсөн матрицын $p_{2}$-р баганаас тус тус тогтоно гэсэн үг юм.

Орчуулсан: Энхгэрэл

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

Оролт
3 3
1 -1 -1
1 2 1
2 -1 1
Гаралт
3 1 2 
Оролт
2 3
1 2 2
2 5 4
Гаралт
1 3 2 
Оролт
2 3
1 2 3
3 2 1
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...