printРабочее место участника

printЗадачи

2056. Телесъёмка

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Для съёмок финального матча "Ротор-Закат" была нанята лучшая съёмочная группа. Несмотря на то, что их работа была выполнена на высочайшем уровне, после просмотра записи выяснилось, что один из игроков Заката ни разу не попал в кадр. Но тренеру интересны действия всех игроков, в том числе и того, которого не оказалось на записи.
Для упрощения задачи будем считать, что игровое поле представляет собой клетчатый прямоугольник `w\ times\ h` клеток. Каждую секунду игрок обязательно перебегает в соседнюю по стороне клетку. Съёмка же является последовательностью из `n` кадров, в каждом из которых видно какой-то подпрямоугольник поля с противоположными углами в `(x_{i_1},\ y_{i_1})` и `(x_{i_2},\ y_{i_2})`. Так как известно, что этот игрок ни разу не попал в кадр, содержимое кадров не важно, важно лишь то, какой участок поля снимался в каждый момент времени.
Ваша задача – помочь тренеру и восстановить какой-либо маршрут, по которому мог перемещаться игрок.
В первой строке заданы натуральные числа `w` и `h` (`1\ ≤\ w,\ h\ ≤\ 300`) – ширина и длина поля. Во второй строке задано число `n` (`1\ ≤\ n\ ≤\ 300`) – число кадров съёмки.
В следующих `n` строках задано по четыре числа `x_{i_1}`, `y_{i_1}`, `x_{i_2}` и `y_{i_2}` (`1\ ≤\ x_{i_1}\ ≤\ x_{i_2}\ ≤\ w`, `1\ ≤\ y_{i_1}\ ≤\ y_{i_2}\ ≤\ h`) – прямоугольник, соответствующий видимой на `i`-м кадре части поля.
Выведите `n` строк, в каждой из которых должно быть по два числа `x_i` и `y_i` (`1\ ≤\ x_i\ ≤\ w`, `1\ ≤\ y_i\ ≤\ 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
Источник: neerc.ifmo.ru/school
loading