• Путешествие
  Ю.Пасихов, Г.Непомнящий, Г.Кравец
  TRAVEL

Описание
Задан полигон в виде прямоугольного клеточного поля размером MxN клеток (M и N, определяют размеры полигона вдоль осей Ox и Оy соответственно). В углах полигона и, возможно, на сторонах размещены выходы, каждый размером в одну клетку. Левый нижний выход имеет координаты (1,1). Граничные клетки полигона, не являющиеся выходами, образуют упругие стенки

Робот начинает движение с клетки с координатами K, L в одном из восьми направлений (вертикально, горизонтально и по двум диагоналям в обоих направлениях). Робот двигается только по целым клеткам и, натолкнувшись на стенку, поворачивает, придерживаясь правила: угол при столкновении равен углу при отталкивания (относительно стены), и далее продолжает движение в полученном направлении с той же скоростью. 

Задача
Необходимо выяснить: останется ли робот на полигоне или покинет его через один из выходов. В последнем случае указать координаты выхода и количество столкновений со стенками. Направления движения Т нумеруются числами от 1 до 8 по часовой стрелке. Направление 1 - вдоль оси Y в направлении увеличения координаты (вверх).

Технические условия

Входной файл: TRAVEL.IN
Выходной файл: TRAVEL.OUT

Входной файл
Входной файл содержит в строке: два натуральных числа M и N (3<=M<=1001), (3<=N<=1001), количество не угловых выходов V (0<=V<=255), затем - V пар натуральных чисел - X и Y координаты не угловых выходов, начальные координаты робота K, L и направление T.  Все величины вводятся через пробел.

Выходной файл
В выходной файл выведите 0, если робот не может найти выход, а если нашел - три числа через пробел - координаты выхода и количество столкновений. 


Например:  

TRAVEL.IN
14  6  1  10  1  13  5  8

TRAVEL.OUT
14  6  13



TRAVEL.IN
11  6  0  4  3  3

TRAVEL.OUT
0