맨해튼 산책

Farmer John과 그의 $Q$마리 소 ($1 \le Q \le 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$ 이하의 정수이다.

Farmer John은 각 소가 어디서 걷기 시작했고 몇 초 전에 탈출했는지 정확히 알고 있다. 소들은 매우 예측 가능하게 움직이며, 각 소는 다음 규칙을 따른다.

• 소는 초당 1 단위로 북($+y$) 또는 동($+x$)으로만 걷는다.
• 소가 도로 하나 위에 있으면, 그 도로의 방향으로 계속 걷는다.
• 소가 두 도로의 교차점에 있으면, 걷기 시작한 뒤 걸은 시간이 짝수 초이면 북쪽으로, 아니면 동쪽으로 걷는다.

맨해튼의 도로 배치와 각 소의 정보가 주어졌을 때, Farmer John이 소들이 지금 어디에 있는지 알아낼 수 있도록 도와라.

첫 줄에 $N$과 $Q$가 주어진다.

다음 $N$개 줄에는 도로가 주어진다. 각 도로는 방향 H 또는 V와 좌표 $c_i$로 나타낸다. 도로는 모두 서로 다르다고 보장된다.

다음 $Q$개 줄에는 소가 주어진다. 각 소는 세 정수 $(x_i, y_i, d_i)$로 나타내며, 이는 소가 $(x_i, y_i)$에서 정확히 $d_i$초 전에 걷기 시작했다는 뜻이다. $(x_i, y_i)$는 어떤 도로 위에 있다고 보장되며, $0 \le x_i, y_i, d_i \le 10^9$이다.

$Q$개 줄을 출력한다. $i$번째 줄에는 $i$번째 소의 현재 위치를 출력한다.