F. Игра с отрезанием
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб снова играли в игру. У них есть клетчатое поле размера $$$a \times b$$$ ($$$1 \le a, b \le 10^9$$$), на котором расположены $$$n$$$ фишек, в каждой клетке может быть не более одной фишки. Клетка на пересечении $$$x$$$-й строки и $$$y$$$-го столбца имеет координаты $$$(x, y)$$$.

Первой ходила Алиса, игроки ходили по очереди. На каждом ходу игрок мог отрезать несколько (но не все) строк или столбцов с начала или конца оставшегося поля и получить очко за каждую фишку, которая находилась на отрезанной части поля. Каждый ход может быть описан символом 'U', 'D', 'L' или 'R' и числом $$$k$$$:

  • Если символ равен 'U', то будут отрезаны $$$k$$$ первых строк среди оставшихся;
  • Если символ равен 'D', то будут отрезаны $$$k$$$ последних строк среди оставшихся;
  • Если символ равен 'L', то будут отрезаны $$$k$$$ первых столбцов среди оставшихся;
  • Если символ равен 'R', то будут отрезаны $$$k$$$ последних столбцов среди оставшихся.

По изначальному состоянию поля и ходам игроков определите количество очков, заработанное Алисой и Бобом соответственно.

Входные данные

Первая строка содержит одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите два целых числа — количество очков, заработанное Алисой и Бобом соответственно.

Пример
Входные данные
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
Выходные данные
2 1
2 0
0 3
1 1
2 0
0 1
Примечание

Ниже показана игра из первого примера:

На своём ходу Алиса отрезала $$$2$$$ строки снизу и получила $$$2$$$ очка, после Боб отрезал $$$1$$$ столбец справа и получил одно очко. Обратите внимание, что если бы Боб отрезал $$$1$$$ строку снизу, он также получил бы $$$1$$$ очко.