Alice 和 Bob 又在玩游戏了。他们有一个大小为 $$$a \times b$$$ ($$$1 \le a, b \le 10^9$$$) 的网格,网格上有 $$$n$$$ 个筹码,每个单元格中最多有一个筹码。第 $$$x$$$ 行和第 $$$y$$$ 列交叉处的单元格的坐标为 $$$(x, y)$$$。
Alice先走一步,玩家轮流走。在每次移动中,玩家可以从剩余网格的开头或结尾处切割几行(但不是全部)行或列,并为网格切割部分上的每个芯片赢得一分。每个动作都可以用字符 'U'、'D'、'L' 或 'R' 以及整数 $$$k$$$ 来描述:
- 如果字符是“U”,则前 $$$k$$$ 剩余行将被剪切;
- 如果字符是“D”,则最后 $$$k$$$ 剩余行将被剪切;
- 如果字符是“L”,则前 $$$k$$$ 剩余列将被剪切;
- 如果字符是“R”,则最后 $$$k$$$ 剩余列将被剪切。
根据网格的初始状态和玩家的动作,分别确定 Alice 和 Bob 获得的分数。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含四个整数 $$$a$$$、$$$b$$$、$$$n$$$ 和 $$$m$$$ ($$$2 \le a, b \le 10^9$$$, $$$1 \le n, m \le 2 \cdot 10^5$$$) — 网格的尺寸、芯片的数量和芯片的数量移动。
接下来的 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i \le a$$$, $$$1 \le y_i \le b$$$) — 筹码的坐标。所有坐标对都是不同的。
接下来的 $$$m$$$ 行包含一个字符 $$$c_j$$$ 和一个整数 $$$k_j$$$ - 第 $$$j$$$ 步棋的描述。保证$$$k$$$小于当前网格的行/列数。换句话说,玩家无法在移动时切掉整个剩余的网格。
保证测试中所有测试用例的 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。保证测试中所有测试用例的 $$$m$$$ 值之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出两个整数——分别是 Alice 和 Bob 获得的点数。
示例
输入 #1
6 4 4 3 2 4 1 3 3 2 4 D 2 R 1 4 4 3 3 4 1 3 2 2 3 D 1 L 1 U 2 3 5 3 2 1 3 2 2 3 3 R 2 R 2 6 4 4 2 1 4 2 3 5 3 1 1 R 1 U 1 9 3 2 1 6 1 3 3 D 8 10 10 2 5 7 5 9 1 R 1 L 2 D 1 U 4 D 1
输出 #1
2 1 2 0 0 3 1 1 2 0 0 1
注意
下面是第一个示例中的游戏:
轮到爱丽丝从底部切掉 $$$2$$$ 行并获得 $$$2$$$ 分,然后鲍勃从右侧切掉 $$$1$$$ 列并获得一分。请注意,如果鲍勃从底部切掉 $$$1$$$ 行,他也会获得 $$$1$$$ 分。