K. Kickball
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$n$$$ schoolchildren playing kickball on an infinite grid. Of course, everyone wants to be the kicker, so they plan to line up. However, they have not figured out how to make a line.

Instead of lining up in an orderly fashion, they wander around an infinite 2-d grid, doing the following every minute:

  • First, each person currently on the grid counts the total number of people on the line perpendicular to the line formed by the direction they are facing in and their current position (including other people at the same position as them). If they count an odd number of people, they will turn $$$90^{\circ}$$$ to their right (in the clockwise direction).
  • Next, every person on the grid will move $$$1$$$ unit in the direction they are facing. Note that multiple people can be on the same point on the grid at the same time.

The $$$i$$$-th person enters the grid at the beginning of minute $$$t_i$$$, facing north, at position $$$(x_i, y_i)$$$. Since recess ends after $$$m$$$ minutes, you need to determine the location of each person at the beginning of minute $$$m$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$  — the number of people and the duration of recess ($$$1 \le n, m \le 1000$$$).

The next $$$n$$$ lines contain three integers $$$x_i, y_i,$$$ and $$$t_i$$$ each, the location and time at which each person joins $$$(1 \le x_i, y_i \le 10^8, 0 \le t_i \lt m)$$$.

It is guaranteed that $$$t_i \leq t_{i + 1}$$$ for all $$$1 \le i \lt n$$$.

Output

Print $$$n$$$ lines consisting of two integers $$$x_i$$$ and $$$y_i$$$ — the location of the $$$i$$$-th person at the beginning of the $$$m$$$-th minute.

Examples
Input
3 5
1 2 0
4 4 2
5 6 4
Output
4 4
7 4
5 7
Input
5 5
1 1 1
5 1 2
1 2 2
3 5 4
4 5 4
Output
1 1
5 4
1 1
4 5
5 5
Note

The first sample case is shown in the following images: