На координатной сетке расположено прямоугольное поле с противоположными углами в точках (0, 0) и (w, h). По линиям сетки внутри поля бегают k муравьев. Каждый муравей может бежать в одном из 4 направлений и со скоростью 1 клетка в секунду.

Так как муравьи очень гордые создания, они никогда не уступают дорогу. Поэтому, если два муравья сталкиваются лоб в лоб, они мгновенно разворачиваются и продолжают идти в обратном направлении. Если два муравья, бегут перпендикулярно не обращают никакого внимания друг на друга. Если же муравей достигает границы поля, то он также разворачивается и бежит обратно.

Вам дано положение и направление движения всех муравьев в начальный момент времени. Определите их положение и направление движения через t секунд.

Входные данные

Первая строка содержит 4 целых числа: w, h, k, t (1 ≤ w, h, k ≤ 100, 1 ≤ t ≤ 109).

Каждая из следующих k строк содержит по 3 целых числа: xi, yi, di, где (xi, yi) - координаты муравья, di - направление его движения (0 < xi < w, 0 < yi < h, 1 ≤ di ≤ 4). di = 1, если муравей двигается в сторону увеличения x, di = 2 - в сторону увеличения y, di = 3 - в сторону уменьшения x, di = 4 - в сторону уменьшения y.

Все числа в строках разделены пробелом. Все муравьи находятся в разных точках.

Выходные данные

Вывести ровно k строк - по одной для каждого муравья в том же порядке, в котором информация о них дается во входе. Каждая строка должна содержать по 3 целых числа, разделенных пробелом - координаты муравья и направление его движения.