ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1364. Поймать Лару

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Кладбище имеет форму прямоугольника в котором N рядов могил по M могилок в каждом ряду. Кладбище по-прежнему окружено высоким и глубоким забором. Как вы уже знаете, Лара Крофт проникла на кладбище через подкоп с северо-западного угла с целью добыть спрятанные в могилах сокровища. Для этого она прорыла длинный подземный ход по такому правилу: если дальше по ходу движения хода находилась целая могилка, то Лара за одну ночь удлиняла ход и разоряла эту могилу. Если же впереди была стенка кладбища или уже разорённая могилка, то Лара поворачивала на 90 градусов вправо и продолжала свое подлое дело. Вы, наверное, уже в курсе, что одно из сокровищ она уже нашла. И скоро найдет второе. Однако, Лара не знает, что тёмные силы решили устроить ей ловушку. Как только Лара найдет оставшееся сокровище (и сразу пойдёт за вторым ящиком шампанского), активируется охранная сигнализация компании "LaraKiller".
Сначала включится башня с всевидящим оком, которое скоро засечёт местоположение Лары. После этого сразу запустится процесс оживления скелетов в разорённых могилах. Скелеты оживают всего за T секунд, и только вот за эти T секунд Лара может куда-нибудь убежать.
Вам, как главному программисту "LaraKiller" и преданному борцу с расхитителями гробниц, необходимо рассчитать, где, к моменту полного оживления скелетов, может оказаться Лара. Лишних скелетов оживлять ни к чему, а то убивать их заставят вас самих.
Очевидно, что Лара будет бежать по своему подземному ходу, причём со скоростью не более 1 могилки в секунду.

Исходные данные

В первой строке находится два числа N и M. 2 ≤ N,M ≤ 100, размеры кладбища. Во второй строке находятся координаты могилки с сокровищем. В третьей строке — координаты Лары в момент включения всевидящего ока. В четвёртой — число T.
Будем считать, что северо-западная могилка имеет координаты (1, 1) а юго-восточная — (N, M). Лара начинала копать свой ход с могилки (1, 1), двигаясь на восток, то есть, к могилке (1, 2).

Результат

Вывести координаты всех могилок в которых может оказаться Лара через T секунд после включения всевидящего ока. Координаты каждой могилки выводить в отдельной строке. Числа разделять пробелом. Могилки должны быть упорядочены по возрастанию расстояния, которое должна пробежать Лара из этой могилки до выхода из кладбища.

Пример

исходные данныерезультат
5 4
4 3
2 2
5
5 2
5 1
4 1
3 1
2 1
2 2
2 3
3 3
4 3
Автор задачи: Станислав Васильев
Источник задачи: IX Чемпионат Урала по спортивному программированию. Екатеринбург, УрГУ, 19-24 апреля 2005 г.