Codeforces Round 946 (Div. 3) |
---|
Закончено |
Алиса и Боб снова играли в игру. У них есть клетчатое поле размера $$$a \times b$$$ ($$$1 \le a, b \le 10^9$$$), на котором расположены $$$n$$$ фишек, в каждой клетке может быть не более одной фишки. Клетка на пересечении $$$x$$$-й строки и $$$y$$$-го столбца имеет координаты $$$(x, y)$$$.
Первой ходила Алиса, игроки ходили по очереди. На каждом ходу игрок мог отрезать несколько (но не все) строк или столбцов с начала или конца оставшегося поля и получить очко за каждую фишку, которая находилась на отрезанной части поля. Каждый ход может быть описан символом 'U', 'D', 'L' или '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$$$.
Для каждого набора входных данных выведите два целых числа — количество очков, заработанное Алисой и Бобом соответственно.
64 4 3 24 13 32 4D 2R 14 4 3 34 13 22 3D 1L 1U 23 5 3 21 32 23 3R 2R 26 4 4 21 42 35 31 1R 1U 19 3 2 16 13 3D 810 10 2 57 59 1R 1L 2D 1U 4D 1
2 1 2 0 0 3 1 1 2 0 0 1
Ниже показана игра из первого примера:
На своём ходу Алиса отрезала $$$2$$$ строки снизу и получила $$$2$$$ очка, после Боб отрезал $$$1$$$ столбец справа и получил одно очко. Обратите внимание, что если бы Боб отрезал $$$1$$$ строку снизу, он также получил бы $$$1$$$ очко.
Название |
---|