Problem 1. Walking in Manhattan

USACO 2024 January Contest, Gold

Farmer John 和他的 $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$ 范围内的整数。

Farmer John 准确地知道每头奶牛从哪里开始行走，以及她们多久之前逃跑的。奶牛们很容易被预测，因此每头奶牛都是按照以下模式行走：

• 她们只会以每秒一个单位的速度向北（$+y$）或向东（$+x$）行走。
• 如果她们当前在一条道路上，她们会继续沿着道路的方向行走。
• 如果她们在两条道路的交叉口处，如果她们行走了偶数秒，则向北行走，否则向东行走。

给定曼哈顿的布局以及每头奶牛的信息，帮助 Farmer John 求出他的奶牛们现在在哪里！

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $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 10

输出样例：

14 5
7 13
6 15
6 16
110 4

前两头奶牛经过的路径如下：

(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

测试点性质： 测试点 2-4：$N, Q, c_i, x_i, y_i, d_i \leq 100$。测试点 5-9：$N, Q\le 3000$。测试点 10-20：没有额外限制。

供题：Benjamin Qi