Луч света
Свет мой, зеркальце! Скажи,
Да всю всю правду доложи,
Мне поведай по секрету,
Ставить где источник света?
Разговор студента Института Точной Магии и Оптики с Волшебным Зеркалом
На координатной плоскости есть поле, ограниченное квадратом с вершинами (0, 0), (N, 0), (N, N), (0, N). В некоторых внутренних точках поля с целочисленными координатами установлены двухсторонние зеркала, расположенные под углом 45° к координатной оси и отражающие свет (в каждой точке может находиться не более одного зеркала, которое устанавливается так, чтобы его центр совпал с соответствующей точкой). На границе зеркал нет. Зеркала бывают двух типов: зеркала первого типа параллельны прямой x + y = 0, а второго типа - прямой x – y = 0. Все зеркала имеют пренебрежимо малую толщину. Примеры отражения луча зеркалами разного типа изображены на рисунках.
Зеркало второго типа Зеркало первого типа
Кроме того, на правой границе в точке с координатами (N, T) находится мишень, в которую нужно попасть лучом.
Напишите программу, которая найдет точку с целочисленными координатами на границе, в которой можно расположить источник света таким образом, чтобы свет, пройдя по полю и возможно отразившись от нескольких зеркал, попал в заданную мишень.
Источник света не может располагаться в одной точке с мишенью и должен быть установлен таким образом, чтобы испускаемый им луч был перпендикулярен границе в этой точке.
Входные данные
В первой строке находится три целых числа: размер поля N, координата точки с мишенью T и количество зеркал на поле M (0 < T < N < 500, 0 <= M <= (N-1)^2). Далее идет M строк, каждая из которых описывает одно зеркало тремя целыми числами x, y и a, где (x, y) - координаты точки, в которой расположено зеркало (0 < x, y < N), a - тип зеркала (1 или 2).
Выходные данные
В первой строке выведите два целых числа – координаты точки на границе поля, в которой должен находиться источник света. Во второй строке выведите целое число, определяющее, сколько раз луч отразится в зеркалах по пути от источника до мишени. Если такой точки не существует, выведите одно число -1. Если таких точек несколько, можно выбрать любую из них.