B. Multitasking

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

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

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

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

Иахуб өөрийн multitasking чадвараа сайжруулахаар шийджээ. Үүнийг хийхийн тулд тэрээр n ширхэг m ширхэг бүхэл тоо агуулсан массивийг эрэмбэлэхээр болжээ.

Иахуб $i$ ба $j$ ($1 ≤ i$, $j ≤ m$, $i ≠ j$) гэсэн 2 хосыг сонгож чадна. Массив бүрийн хувьд $i$ ба $j$ дүгээрх элементийн утга зөвхөн $i$ дахь элементийн утга $j$-ийнхээс бага үед солигдоно.

Иахуб хоёр хос элемент сонгох замаар өгөгдсөн бүх массивийг өсөх эсвэл буурахаар (өсөх буурах аль нь болохыг оролт дээр өгнө) эрэмбэлэх ёстой. Массивийн хэмжээ нь хамгийн ихдээ enter image description here (хамгийн ихдээ enter image description here хос). Иахуб-д тохиромжтой массивийг олоход туслаарай.

Оролт

Эхний мөрөнд $n$ ($1 ≤  n ≤ 1000$), $m$ ($1 ≤ m ≤  100$), $k$ гурван тоо. $k$ нь 0 үед массивууд өсөхөөр, 1 үед буурахаар эрэмбэлэгдэх ёстой. Дараагийн $n$ ширхэг мөрийн $i$-р мөр болгон $m$ ширхэг зайгаар тусгаарлагдсан тоонууд агуулна. $i$-р массивийн $x$ элемент бүрийн хувьд $1 ≤ x ≤ 106$ утга хадгална.

Гаралт

Эхний мөрөнд $p$ бүхэл тоо, массивын хэмжээ ($p$ хамгийн их утгаараа байж болно). Дараагийн $p$ ширхэг мөрөнд $i$, $j$ ($1 ≤ i$,$ j ≤ m$,$ i ≠ j$) тоонууд сонгогдсон хосуудыг илтгэнэ.

Хэрвээ олон хариутай бол алийг нь ч хэвлэсэн болно.

Орчуулсан: Баттулга

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

Оролт
2 5 0
1 3 2 5 4
1 4 3 2 5
Гаралт
3
2 4
2 3
4 5
Оролт
3 2 1
1 2
2 3
3 4
Гаралт
1
2 1

Тэмдэглэл

Consider the first sample. After the first operation, the arrays become $[1, 3, 2, 5, 4]$ and $[1, 2, 3, 4, 5]$. After the second operation, the arrays become $[1, 2, 3, 5, 4]$ and $[1, 2, 3, 4, 5]$. After the third operation they become $[1, 2, 3, 4, 5]$ and $[1, 2, 3, 4, 5]$.

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