Farmer John and his Q(1≤Q≤2⋅105) cows are in Manhattan on vacation, but the cows have escaped and are now walking around freely in the city! Manhattan is huge – so huge that its N (1≤N≤2⋅105) roads stretch infinitely in the x-y plane, but conveniently, those roads all run perfectly horizontally or vertically. Each horizontal and vertical road can be modeled by an equation of the form y= ci or x=ci , where ci is an integer in the range 0 to 109 inclusive.
Farmer John knows exactly where each cow started walking and how long ago they escaped. Cows are very predictable, so each of them walks according to the following pattern:
They only walk north (+y) or east (+x) at one unit per second.
If they are currently on a single road, they continue walking along the road's direction.
If they are at the intersection of two roads, they walk north if they have been walking for an even number of seconds and east otherwise.
Given the layout of Manhattan and the information for each cow, help Farmer John determine where his cows are now!
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N and Q.
The next N lines describe the roads. Each road is described by a direction (H or V) and a coordinate ci. It is guaranteed that the roads are unique.
The next Q lines describe the cows. Each cow is described by three integers (xi,yi,di), meaning that they started walking from (xi,yi) exactly di seconds ago. It is guaranteed that (xi,yi) lies on some road, and 0≤xi,yi,di≤109 .
OUTPUT FORMAT (print output to the terminal / stdout):
Output Q lines, where the ith line contains the current position of the ith cow.
SAMPLE INPUT:
4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10
SAMPLE OUTPUT:
14 5
7 13
6 15
6 16
110 4
The first two cows took the following paths:
(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)
SCORING:
Inputs 2-4 satisfy N,Q,ci,xi,yi,di≤100.
Inputs 5-9 satisfy N,Q≤3000.
Inputs 10-20 satisfy no additional constraints.
Problem credits: Benjamin Qi
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
