codeforces#P1974F. Cutting Game

    ID: 34673 远端评测题 3000ms 256MiB 尝试: 1 已通过: 0 难度: 6 上传者: 标签>binary searchbrute forcedata structuresimplementationsortingstwo pointers*1900

Cutting Game

Description

Alice and Bob were playing a game again. They have a grid of size a×ba \times b (1a,b1091 \le a, b \le 10^9), on which there are nn chips, with at most one chip in each cell. The cell at the intersection of the xx-th row and the yy-th column has coordinates (x,y)(x, y).

Alice made the first move, and the players took turns. On each move, a player could cut several (but not all) rows or columns from the beginning or end of the remaining grid and earn a point for each chip that was on the cut part of the grid. Each move can be described by the character 'U', 'D', 'L', or 'R' and an integer kk:

  • If the character is 'U', then the first kk remaining rows will be cut;
  • If the character is 'D', then the last kk remaining rows will be cut;
  • If the character is 'L', then the first kk remaining columns will be cut;
  • If the character is 'R', then the last kk remaining columns will be cut.

Based on the initial state of the grid and the players' moves, determine the number of points earned by Alice and Bob, respectively.

The first line contains a single integer tt (1t1041 \le t \le 10^4) — the number of test cases.

The first line of each test case contains four integers aa, bb, nn, and mm (2a,b1092 \le a, b \le 10^9, 1n,m21051 \le n, m \le 2 \cdot 10^5) — the dimensions of the grid, the number of chips, and the number of moves.

Each of the next nn lines contain two integers xix_i and yiy_i (1xia1 \le x_i \le a, 1yib1 \le y_i \le b) — the coordinates of the chips. All pairs of coordinates are distinct.

Each of the next mm lines contain a character cjc_j and an integer kjk_j — the description of the jj-th move. It is guaranteed that kk is less than the number of rows/columns in the current grid. In other words, a player cannot cut the entire remaining grid on their move.

It is guaranteed that the sum of the values of nn across all test cases in the test does not exceed 21052 \cdot 10^5. It is guaranteed that the sum of the values of mm across all test cases in the test does not exceed 21052 \cdot 10^5.

For each test case, output two integers — the number of points earned by Alice and Bob, respectively.

Input

The first line contains a single integer tt (1t1041 \le t \le 10^4) — the number of test cases.

The first line of each test case contains four integers aa, bb, nn, and mm (2a,b1092 \le a, b \le 10^9, 1n,m21051 \le n, m \le 2 \cdot 10^5) — the dimensions of the grid, the number of chips, and the number of moves.

Each of the next nn lines contain two integers xix_i and yiy_i (1xia1 \le x_i \le a, 1yib1 \le y_i \le b) — the coordinates of the chips. All pairs of coordinates are distinct.

Each of the next mm lines contain a character cjc_j and an integer kjk_j — the description of the jj-th move. It is guaranteed that kk is less than the number of rows/columns in the current grid. In other words, a player cannot cut the entire remaining grid on their move.

It is guaranteed that the sum of the values of nn across all test cases in the test does not exceed 21052 \cdot 10^5. It is guaranteed that the sum of the values of mm across all test cases in the test does not exceed 21052 \cdot 10^5.

Output

For each test case, output two integers — the number of points earned by Alice and Bob, respectively.

输入数据 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

Note

Below is the game from the first example:

On her turn, Alice cut 22 rows from the bottom and scored 22 points, then Bob cut 11 column from the right and scored one point. Note that if Bob had cut 11 row from the bottom, he would have also scored 11 point.