← 返回题目列表

Codeforces · 1974/F

F. 切割游戏

中文机器翻译题面 查看原题

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$$$ 分。