Муравьи
На координатной сетке расположено прямоугольное поле с противоположными углами в точках (0, 0) и (w, h). По линиям сетки внутри поля бегают k муравьев. Каждый муравей может бежать в одном из 4 направлений и со скоростью 1 клетка в секунду.
Так как муравьи очень гордые создания, они никогда не уступают дорогу. Поэтому, если два муравья сталкиваются лоб в лоб, они мгновенно разворачиваются и продолжают идти в обратном направлении. Если два муравья, бегут перпендикулярно не обращают никакого внимания друг на друга. Если же муравей достигает границы поля, то он также разворачивается и бежит обратно.
Вам дано положение и направление движения всех муравьев в начальный момент времени. Определите их положение и направление движения через t секунд.
Входные данные
Первая строка содержит 4 целых числа: w, h, k, t (1 ≤ w, h, k ≤ 100, 1 ≤ t ≤ 10^9).
Каждая из следующих k строк содержит по 3 целых числа: x[i], y[i], d[i], где (x[i], y[i]) - координаты муравья, d[i] - направление его движения (0 < x[i] < w, 0 < y[i] < h, 1 ≤ d[i] ≤ 4). d[i] = 1, если муравей двигается в сторону увеличения x, d[i] = 2 - в сторону увеличения y, d[i] = 3 - в сторону уменьшения x, d[i] = 4 - в сторону уменьшения y.
Все числа в строках разделены пробелом. Все муравьи находятся в разных точках.
Выходные данные
Вывести ровно k строк - по одной для каждого муравья в том же порядке, в котором информация о них дается во входе. Каждая строка должна содержать по 3 целых числа, разделенных пробелом - координаты муравья и направление его движения.