Cows in Manhattan

Farmer John is vacationing in Manhattan with his \(Q\) cows. Unfortunately, the cows have escaped and are wandering around the city. Manhattan has \(N\) roads that extend infinitely in the plane. Each road is either horizontal or vertical and is represented by an equation \(x=c\) (vertical) or \(y=c\) (horizontal), where \(0\le c\le 10^9\).

Each cow starts at a given position and began walking \(t\) seconds ago. The cows walk at a speed of one unit per second according to the following rules:

• If a cow is on a single road, it continues in the road’s natural direction: north (\(+y\)) for vertical roads and east (\(+x\)) for horizontal roads.
• If a cow is at an intersection (i.e. its position satisfies both \(x=c_1\) and \(y=c_2\) for some roads), then it chooses its direction based on how many seconds it has walked so far: if it has walked an even number of seconds, it moves north; if odd, it moves east.

Given the road layout and the initial positions and walking times of the cows, determine the final location of each cow after \(t\) seconds.

inputFormat

The first line contains two integers \(N\) and \(Q\): the number of roads and the number of cows. The next \(N\) lines each describe a road in one of the following formats:

• x c — a vertical road given by \(x=c\)
• y c — a horizontal road given by \(y=c\)

It is guaranteed that \(0\le c\le 10^9\). The following \(Q\) lines each contain three integers \(x\), \(y\), and \(t\), representing the starting position \((x,y)\) of a cow (which is guaranteed to lie on at least one road) and the number of seconds the cow has been walking.

outputFormat

For each cow, output a line containing two integers: the final \(x\) and \(y\) coordinates of the cow after \(t\) seconds.

sample

2 1
y 5
x 3
1 5 5

3 8