Промінь світла
Свет мой, зеркальце! Скажи,
Да всю всю правду доложи,
Мне поведай по секрету,
Ставить где источник света?
Розмова студента Інституту Точної Магії і Оптики з Чарівним Зеркалом
На координатній площині є поле, обмежене квадратом з вершинами (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. Якщо таких точок декілька, можна вибрати довільну з них.