| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 33 | 9 | 8 | 50.000% |
Для съёмок финального матча <<Ротор--Закат>> была нанята лучшая съёмочная группа. Несмотря на то, что их работа была выполнена на высочайшем уровне, после просмотра записи выяснилось, что один из игроков Заката ни разу не попал в кадр. Но тренеру интересны действия всех игроков, в том числе и того, которого не оказалось на записи.
Для упрощения задачи будем считать, что игровое поле представляет собой клетчатый прямоугольник $w \times h$ клеток. Каждую секунду игрок обязательно перебегает в соседнюю по стороне клетку. Съёмка же является последовательностью из $n$ кадров, в каждом из которых видно какой-то подпрямоугольник поля с противоположными углами в $(x_{i_1}, y_{i_1})$ и $(x_{i_2}, y_{i_2})$. Так как известно, что этот игрок ни разу не попал в кадр, содержимое кадров не важно, важно лишь то, какой участок поля снимался в каждый момент времени.
Ваша задача --- помочь тренеру и восстановить какой-либо маршрут, по которому мог перемещаться игрок.
В первой строке заданы натуральные числа $w$ и $h$ (1ドル \le w, h \le 300$) --- ширина и длина поля. Во второй строке задано число $n$ (1ドル \le n \le 300$) --- число кадров съёмки.
В следующих $n$ строках задано по четыре числа $x_{i_1},ドル $y_{i_1},ドル $x_{i_2}$ и $y_{i_2}$ (1ドル \le x_{i_1} \le x_{i_2} \le w,ドル 1ドル \le y_{i_1} \le y_{i_2} \le h$) --- прямоугольник, соответствующий видимой на $i$-м кадре части поля.
Выведите $n$ строк, в каждой из которых должно быть по два числа $x_i$ и $y_i$ (1ドル \le x_i \le w,ドル 1ドル \le y_i \le h$) --- координаты клетки, в которой мог оказаться этот игрок на $i$-й секунде. Выведите <<Impossible>>, если не могло быть такой ситуации, что игрок не попал ни на один из кадров.
3 2 5 1 1 2 1 2 1 2 1 2 2 3 2 2 2 3 2 2 1 2 2
1 2 2 2 2 1 3 1 3 2