题目描述

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$ 列的交叉处。你应在两个数字之间恰好输出一个空格。

对于每个第二类查询（“!”），输出一行包含一个整数，表示当前位于同一个方格内的车的对数。

1
4 9
3 4
2 1
4 2
1 3
L 2
? 1
? 2
R 1
? 1
? 3
!
U 3
!

3 2
2 1
3 3
4 2
0
3

提示

下列各图展示了样例中棋盘在初始时及每次最高指令后的状态。

:::align{center} :::

翻译由 DeepSeek V4 Pro 完成