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 \le n, m \le 3 \times 10^5$。

接下来的 $n$ 行，每行包含两个整数 $x$ 和 $y$，描述一个位于第 $x$ 行第 $y$ 列交叉点的车，其中 $1 \le x, y \le n$。

随后 $m$ 行按时间顺序描述了所有的至高指令和查询，其中所有给定的参数 $k$ 均为 $1$ 到 $n$ 之间的整数。

我们保证所有测试用例中 $n$ 的总和与 $m$ 的总和分别不超过 $10^6$。

输出格式

对于每个测试用例，输出若干行以回答所有查询。

对于第一种类型的查询（? k），输出一行，包含两个整数 $x$ 和 $y$，表示第 $k$ 号车当前位于第 $x$ 行第 $y$ 列的交叉点。这两个数字之间应恰好有一个空格。

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

样例

输入格式 1

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

输出格式 1

3 2
2 1
3 3
4 2
0
3

说明

下图展示了样例中棋盘在开始时以及每次至高指令执行后的状态。