Промінь світла#560
О чарівне люстерко, що яскраво сяє!
Розкрий свою мудрість, покажи світло,
Поділись своїм секретом, якщо зможеш:
Де ж розташувати джерело світла?
Студент Академії Таємничої Оптики та Чарів розмовляє з чарівним люстерком.
На координатній площині знаходиться квадратне поле з вершинами у точках , , (N, N) та . Всередині поля, у деяких внутрішніх точках з цілими координатами встановлені двосторонні дзеркала. Ці дзеркала розташовані під кутом 45^\circ до координатних осей і відбивають світло. У кожній точці може бути не більше одного дзеркала, центр якого знаходиться в точці з цілими координатами. На межі поля дзеркал немає. Дзеркала бувають двох типів: дзеркала типу паралельні прямій x + y = 0; дзеркала типу паралельні прямій x - y = 0. Всі дзеркала мають незначну товщину.
На правій межі поля, у точці (N, T), знаходиться ціль, до якої має бути спрямовано світловий промінь.
Напишіть програму, яка знайде таку точку на межі з цілими координатами, де можна розмістити джерело світла так, щоб промінь, виходячи звідти та, можливо, відбиваючись від дзеркал, досягав вказаної цілі.
Джерело світла не можна розташовувати у тій самій точці, що й ціль, і промінь обов'язково повинен бути спрямований перпендикулярно до межі у цій точці.
У першому рядку дано три цілих числа: розмір поля , координату цілі та кількість дзеркал (0 < T < N < 500, 0 \leq M \leq (N-1)^2).
У наступних рядках містяться по три цілих числа , , — координати дзеркала (0 < x, y < N) та його тип ( або ).
Виведіть у першому рядку два цілих числа — координати точки на межі, де слід розташувати джерело світла. У другому рядку виведіть кількість дзеркал, від яких промінь відбиватиметься дорогою до цілі. Якщо такої точки не існує, виведіть . Якщо існує декілька варіантів, дозволяється вивести будь-який з них.
Приклад 1