레이팅 미적용농부 존과 그의 소 \(Q\)마리 (\(1 \leq Q \leq 2 \cdot 10^5\))가 맨해튼으로 휴가를 왔는데, 소들이 탈출해서 도시를 자유롭게 돌아다니고 있다! 맨해튼은 아주 커서 \(N\) (\(1 \le N \le 2 \cdot 10^5\))개의 도로가 \(x\)-\(y\) 평면에서 무한히 뻗어 있지만, 다행히도 모든 도로는 완벽하게 수평 또는 수직으로 나 있다. 각 수평 도로와 수직 도로는 \(y = c_i\) 또는 \(x = c_i\) 형태의 방정식으로 나타낼 수 있으며, \(c_i\)는 \(0\) 이상 \(10^9\) 이하의 정수이다.
농부 존은 각 소가 어디에서 걷기 시작했는지, 얼마나 오래전에 탈출했는지 정확히 알고 있다. 소들은 매우 예측 가능해서 각자 다음 규칙에 따라 걷는다.
- 북쪽 (\(+y\)) 또는 동쪽 (\(+x\))으로만 초당 1단위 속도로 걷는다.
- 현재 도로 하나 위에만 있다면 그 도로의 방향을 따라 계속 걷는다.
- 두 도로의 교차점에 있다면, 지금까지 걸은 시간이 짝수 초이면 북쪽으로, 홀수 초이면 동쪽으로 걷는다.
맨해튼의 도로 배치와 각 소의 정보가 주어질 때, 소들이 지금 어디에 있는지 농부 존이 알아내도록 도와주자!
출제: Benjamin Qi
배점
- 입력 2-4: \(N, Q, c_i, x_i, y_i, d_i \leq 100\).
- 입력 5-9: \(N, Q\le 3000\).
- 입력 10-20: 추가 제약 없음.
출제: Benjamin Qi
첫째 줄에 \(N\)과 \(Q\)가 주어진다.
다음 \(N\)개의 줄에 도로에 대한 설명이 주어진다. 각 도로는 방향(H 또는 V)과 좌표 \(c_i\)로 주어진다. 도로들은 서로 겹치지 않음이 보장된다.
다음 \(Q\)개의 줄에 소에 대한 설명이 주어진다. 각 소는 세 정수 \((x_i, y_i, d_i)\)로 주어지며, 이는 정확히 \(d_i\)초 전에 \((x_i, y_i)\)에서 걷기 시작했다는 뜻이다. \((x_i, y_i)\)는 어떤 도로 위에 있음이 보장되며, \(0 \le x_i, y_i, d_i \le 10^9\)이다.
\(Q\)개의 줄을 출력한다. \(i\)번째 줄에는 \(i\)번째 소의 현재 위치를 출력한다.
4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 1014 5
7 13
6 15
6 16
110 4The 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)