Cowboy

There are N cowboys in the arena, tagged with 1 to N. The arena can be considered as an N * N grid.

At first, every cowboy is standing on a grid point (lower left point is (1,1) and upper right is (N,N)).

Then the god named Matt will give M orders to the cowboys. All orders look like this: (i,dir,distance) which means the i-th cowboy moving distance step in dir direction.

And dir will be:

● '1' for East ((x,y)->(x + 1, y) for one step)
● '2' for North ((x,y)->(x, y + 1) for one step)
● '3' for West ((x,y)->(x - 1, y) for one step)
● '4' for South ((x,y)->(x, y - 1) for one step)

Since the cowboys can't get out of the arena, they will stop moving if they reach the boundary of the arena.

The cowboys are so aggressive that they always want to duel, but only the one that is moving can duel another cowboy. If a cowboy A is given an order, he will first turn his direction to the moving direction.

Then A will look at both his left hand direction and right hand direction, and the point now he is standing. If someone B is insight, A and B will have a duel, and the one with a smaller tag number will be the winner and loser will leave the arena, and A will stop moving immediately.

If no one is insight, A will go one step and start looking again. The process will stop if someone is insight, or A has moved for 'distance' steps and no one is insight.

Since the Cowboys' eyesight is not so good, they can only see someone if the distance between them is no more than D.

Since all cowboys are confident, if there are more than one cowboy insight, they will choose to duel the one with the smallest tag number.

Furthermore, Matt will give an order only if the previous cowboy has stopped. It's possible for more than one cowboy on one point. Nothing will happen if Matt gives an order to a cowboy that has left the arean.

Now, given the initial location of the cowboys and the orders, we want to know the final situation of the arena.

The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow.

For each test case, the first line contains three integers:N,M,D(1<=N<= 50000,M<=50000,0<=D).

In the following N lines, the i-th line contains two integers:X,Y (1<=X, Y <=N) indicating the initial location of the i-th cowboy.

In the following M lines, the i-th line contains three integers:I,Dir,Dis(1<=I <=N, 1<=Dir<=4, 0<=Dis<=N) indicating the i-th order given by Matt.

All the numbers appears in the input will not exceed 10^9.

For each test case, first output one line "Case #x:", where x is the case number (starting from 1).

Then for each cowboy that has not left the arena, output his tag number and final location in one line(Output in tag number order).

1
5 2 1
1 1
5 5
1 5
5 1
3 3
5 4 1
1 1 2

Case #1:
1 3 1
2 5 5
3 1 5
4 5 1

2014 ACM/ICPC Asia Regional Beijing Online