Ants

A rectangular field is $W$ centimeters wide and $H$ centimeters tall, with one corner at $(0, 0)$ and the opposite corner at $(W, H)$. Inside the field, $K$ ants move along the coordinate grid lines at 1 centimeter per second. Each ant moves in one of four directions.

Ants are proud and never give way. When two ants meet head-on, both turn around on the spot and run back the way they came. Two ants moving perpendicular to each other ignore each other, even when they pass through the same point. An ant that reaches the boundary of the field also turns around and runs back.

Turning takes no time. If a head-on meeting or a boundary touch happens exactly at second $T$, report the direction the ant has after the turn.

You are given the starting position and direction of every ant. Find the position and direction of each ant after $T$ seconds.

The first line contains four integers $W$, $H$, $K$, $T$ ($1 \le W, H, K \le 100$, $1 \le T \le 10^9$).

Each of the next $K$ lines contains three integers $X_i$, $Y_i$, $D_i$, where $(X_i, Y_i)$ is the position of the $i$-th ant and $D_i$ is the direction it moves in ($0 < X_i < W$, $0 < Y_i < H$, $1 \le D_i \le 4$). $D_i = 1$ means the ant moves toward increasing $X$, $D_i = 2$ toward increasing $Y$, $D_i = 3$ toward decreasing $X$, and $D_i = 4$ toward decreasing $Y$.

Numbers on one line are separated by single spaces. No two ants start at the same point.

Print $K$ lines, one for each ant, in the same order as the input. Each line holds three integers separated by single spaces: the coordinates of the ant after $T$ seconds and the direction it moves in.