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

Задано прямоугольное поле размера $$$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$$$ независимых наборов тестовых данных.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 < nm \le 10^6$$$) — количество строк и количество столбцов соответственно.

Следующие $$$n$$$ строк содержат по $$$m$$$ символов каждая, где $$$j$$$-й символ $$$i$$$-й строки равен $$$c_{i, j}$$$ ($$$c_{i, j}$$$ равно либо '0', если клетка $$$(i, j)$$$ покрашена в черный цвет, либо '1', если клетка $$$(i, j)$$$ покрашена в белый цвет).

Следующие $$$n$$$ строк также содержат по $$$m$$$ символов каждая, где $$$j$$$-й символ $$$i$$$-й строки равен $$$s_{i, j}$$$ ($$$s_{i, j}$$$ равно 'U', 'R', 'D' или 'L', и описывает направление клетки $$$(i, j)$$$).

Гарантируется, что сумма размеров полей не превосходит $$$10^6$$$ ($$$\sum nm \le 10^6$$$).

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

Для каждого набора тестовых данных выведите два числа — максимальное количество роботов, которое вы можете поставить, чтобы удовлетворить все ограничения, указанные в условии задачи, и максимальное количество черных клеток, в которых находятся роботы перед началом всех перемещений, если количество поставленных роботов максимально. Заметьте, что вы можете ставить роботов только перед началом всех перемещений.

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