P17468 [ICPC 2018 Jiaozuo R] Supreme Command

Lewis 喜欢下棋。现在，他在一个拥有 $n$ 行 $n$ 列的棋盘上放置了 $n$ 个车。棋盘的所有行从上到下依次标号为 $1$ 到 $n$，所有列从左到右依次标号为 $1$ 到 $n$。所有车也同样标号为 $1$ 到 $n$。一开始，**每行或每列恰好包含一个车**。然而，Lewis 允许在对局过程中一个方格内存在两个或更多个车。 现在他开始玩一个名为 Supreme Command 的游戏。他将向所有车发出若干条最高指令。所有可能的指令共有以下四种格式。 * `L k`：每个车向左移动 $k$ 格； * `R k`：每个车向右移动 $k$ 格； * `U k`：每个车向上移动 $k$ 格； * `D k`：每个车向下移动 $k$ 格。 对于给定数字 $k$ 的最高指令，如果某个车在移动不足 $k$ 格时已抵达边界（即位于最左侧列、最右侧列、最上方行或最下方行），导致无法继续移动，则该车将停留在该处而不会移出棋盘。 他还会对车进行若干次查询。查询只有以下两种可能的格式。 * `? k`：询问第 $k$ 个车的当前位置； * `!`：询问当前有多少对车位于同一个方格内。 你在本题中的任务就是正确回答这些查询。

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据组数，最多可达 $1000$。 对于每组测试数据，第一行包含两个整数 $n$，意义如上所述，以及 $m$，表示最高指令与查询的总数，满足 $1 \leq n, m \leq 3 \times 10^5$。 接下来的 $n$ 行，每行包含两个整数 $x$ 和 $y$，描述一个车位于第 $x$ 行与第 $y$ 列的交叉处，满足 $1 \leq x, y \leq n$。 再接下来的 $m$ 行按时间顺序描述所有最高指令与查询，其中所有给定参数 $k$ 均为 $1$ 到 $n$ 之间的整数。 我们保证所有测试数据中 $n$ 的总和与 $m$ 的总和均分别不超过 $10^6$。

对于每组测试数据，输出若干行以回答所有查询。 对于每个第一类查询（“? $k$”），输出一行包含两个整数 $x$ 和 $y$，表示第 $k$ 个车的当前位置为第 $x$ 行与第 $y$ 列的交叉处。你应在两个数字之间恰好输出一个空格。 对于每个第二类查询（“!”），输出一行包含一个整数，表示当前位于同一个方格内的车的对数。

下列各图展示了样例中棋盘在初始时及每次最高指令后的状态。 :::align{center}  ::: 翻译由 DeepSeek V4 Pro 完成