Задано прямоугольное поле размера \(n \times m\). Каждая клетка поля покрашена либо в черный цвет ('0'), либо в белый цвет ('1'). Цвет клетки \((i, j)\) обозначается как \(c_{i, j}\). Вам также задана карта направлений: для каждой клетки указано направление \(s_{i, j}\), которое равно одному из четырех символов 'U', 'R', 'D' и 'L'.
- Если \(s_{i, j}\) равно 'U', то из клетки \((i, j)\) есть переход в клетку \((i - 1, j)\);
- если \(s_{i, j}\) равно 'R', то из клетки \((i, j)\) есть переход в клетку \((i, j + 1)\);
- если \(s_{i, j}\) равно 'D', то из клетки \((i, j)\) есть переход в клетку \((i + 1, j)\);
- если \(s_{i, j}\) равно 'L', то из клетки \((i, j)\) есть переход в клетку \((i, j - 1)\).
Гарантируется, что самая верхняя строка не содержит символов 'U', самая нижняя строка не содержит символов 'D', самый левый столбец не содержит символов 'L' и самый правый столбец не содержит символов 'R'.
Вы хотите поставить роботов на поле (не более одного робота в клетку). При этом следующие условия должны быть соблюдены.
- Во-первых, каждый робот всегда обязан перемещаться (то есть он не может пропустить ход). За один ход каждый робот перемещается в соседнюю клетку в соответствии с текущим направлением.
- Во-вторых, вам необходимо поставить роботов таким образом, что не найдется такого хода, перед которым два различных робота стоят в одной и той же клетке (это также значит, что вы не можете поставить двух роботов в одну и ту же клетку). Таким образом, Если поле равно «RL» (одна строка, два столбца, цвета здесь не важны), то вы можете поставить двух роботов в клетки \((1, 1)\) и \((1, 2)\), но если поле равно «RLL», то вы не можете поставить роботов в клетки \((1, 1)\) и \((1, 3)\), потому что в течение первой секунды оба робота будут стоять в клетке \((1, 2)\).
Роботы делают бесконечное количество ходов.
Ваша задача — поставить максимальное количество роботов таким образом, чтобы удовлетворить все условия, описанные выше, а среди всех таких способов вам необходимо выбрать такой, что количество черных клеток, на которых стоят роботы перед началом всех перемещений является максимально возможным. Заметьте, что вы можете ставить роботов только перед началом всех перемещений.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите два числа — максимальное количество роботов, которое вы можете поставить, чтобы удовлетворить все ограничения, указанные в условии задачи, и максимальное количество черных клеток, в которых находятся роботы перед началом всех перемещений, если количество поставленных роботов максимально. Заметьте, что вы можете ставить роботов только перед началом всех перемещений.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
01
RL
3 3
001
101
110
RLL
DLD
ULL
3 3
000
000
000
RRD
RLD
ULL
|
2 1
4 3
2 2
|