C. Дахин гал гарав

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

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

оролт input.txt

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

Берландад гарсан аймшигт ойн түймрийн дараа ойн дахин сэргээх хөтөлбөрийг хэрэгжүүлэв. Хөтөлбөрийн дагуу $M$ модтой $N$ эгнээнүүдийг тарьсан бөгөөд эгнээнүүд маш ойр байх ба дурын нэгэн үүнийг координатын систем дээр $i$ дахь эгнээний $j$ дэх модыг $(i, j)$ хэмээн координатлах боломжтой байв. Гэвч аймшигт зүйл дахин гарч залуу ойг гал дахин нөмрөв. Одоо бид нүүлгэн шилжүүлэлтийг төлөвлөх үүднээс хамгийн сүүлд галыг барьж байх модны координатыг олох явдал юм.

Гал анх $K$ цэгүүдээс эхэлсэн бөгөөд энэ нь К моднууд хамгийн түрүүнд шатаж эхэлсэн гэсэн үг юм. Минут тутам гал нэг модноос нөгөө модонд дамжих бөгөөд шатаагүй моднууд нь шатаж байгаа модны хоорондын зай $1$-тэй тэнцүү.

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

Оролт

Эхний шугам нь $N, M$ гэсэн $2$ бүхэл тоог агуулж байгаа $(1 ≤ N, M ≤ 2000)$ бөгөөд энэ нь ойн хэмжээг харуулна. Модыг $(x, y) (1 ≤ x ≤ N, 1 ≤ y ≤ M)$-ын бүх цэгт тарисан ба $х, у$ нь бүхэл тоо байна.

Хоёр дахь шугам нь $K (10 ≤ 1 ≤ K)$ бүхэл тоог агуулах бөгөөд энэ нь анх шатаж эхэлсэн модны тоог харуулж байна.

Гурав дахь шугам нь $K$ $x_{1}, y_{1}, x_{2}, y_{2}, ..., x_{k}, y_{k}(1 ≤ x_{i} ≤ N, 1 ≤ y_{i} ≤ M$) гэсэн хос бүхэл тоо агуулж байгуу бөгөөд эдгээр нь гал асч эхэлсэн цэгүүдийн координатуудыг харуулж байна. Энд хоёр цэг нь огтолцохгүй болно.

Гаралт

Хоёр зайгаар тусгаарлагдсан $х, у$ бүхэл тоотой шугамыг үүсгэ. Энэ нь хамгийн сүүлд шатаж эхлэх модны координатууд байна. Хэрэв хэд хэдэн ийм мод байвал аль нэгнийг нь сонго.

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

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

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