Алиса и Боб снова играли в игру. У них есть клетчатое поле размера \(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\) последних столбцов среди оставшихся.
По изначальному состоянию поля и ходам игроков определите количество очков, заработанное Алисой и Бобом соответственно.
Выходные данные
Для каждого набора входных данных выведите два целых числа — количество очков, заработанное Алисой и Бобом соответственно.
Примечание
Ниже показана игра из первого примера:
На своём ходу Алиса отрезала \(2\) строки снизу и получила \(2\) очка, после Боб отрезал \(1\) столбец справа и получил одно очко. Обратите внимание, что если бы Боб отрезал \(1\) строку снизу, он также получил бы \(1\) очко.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
2 1
2 0
0 3
1 1
2 0
0 1
|