{"problem":{"name":"[USACO24JAN] Walking in Manhattan G","description":{"content":"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","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10137"},"statements":[{"statement_type":"Markdown","content":"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$ 范围内的整数。\n\nFarmer John 准确地知道每头奶牛从哪里开始行走，以及她们多久之前逃跑的。奶牛们很容易被预测，因此每头奶牛都是按照以下模式行走：\n\n- 她们只会以每秒一个单位的速度向北（$+y$）或向东（$+x$）行走。\n- 如果她们当前在一条道路上，她们会继续沿着道路的方向行走。\n- 如果她们在两条道路的交叉口处，如果她们行走了偶数秒，则向北行走，否则向东行走。\n\n给定曼哈顿的布局以及每头奶牛的信息，帮助 Farmer John 求出他的奶牛们现在在哪里！\n\n## Input\n\n输入的第一行包含 $N$ 和 $Q$。\n\n以下 $N$ 行描述道路。每条道路由方向（`H` 代表东西向，`V` 代表南北向）和坐标 $c_i$ 表示。输入保证道路各不相同。\n\n以下 $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$。\n\n## Output\n\n输出 $Q$ 行，其中第 $i$ 行包含第 $i$ 头奶牛当前的位置。\n\n[samples]\n\n## Note\n\n### 样例解释 1\n\n前两头奶牛经过的路径如下：\n\n$(6, 3) \\to (6, 4) \\to (7, 4) \\to (7, 5) \\to (8, 5) \\to \\ldots \\to (14, 5)$  \n$(6, 4) \\to (6, 5) \\to (7, 5) \\to (7, 6) \\to \\ldots \\to (7, 13)$\n\n### 测试点性质\n\n- 测试点 $2-4$：$N,Q,c_i,x_i,y_i,d_i\\le 100$。\n- 测试点 $5-9$：$N,Q\\le 3000$。\n- 测试点 $10-20$：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10137","tags":["倍增","USACO","2024","Ad-hoc","分类讨论"],"sample_group":[["4 5\nV 7\nH 4\nH 5\nV 6\n6 3 10\n6 4 10\n6 5 10\n6 6 10\n100 4 10","14 5\n7 13\n6 15\n6 16\n110 4"]],"created_at":"2026-03-03 11:09:25"}}