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

Черепаха Алиса в настоящее время разрабатывает коробку для печенья с предсказаниями, и она хотела бы включить в нее теорию Лоушу.

Коробку можно рассматривать как таблицу размера $$$n \times m$$$ ($$$n, m \ge 5$$$), где строки нумеруются $$$1, 2, \dots, n$$$, а столбцы нумеруются $$$1, 2, \dots, m$$$. Каждая клетка может быть либо пустой, либо содержать одно печенье с предсказанием одной из следующих форм: круг или квадрат. Клетка на пересечении $$$a$$$-й строки $$$b$$$-го столбца обозначается как $$$(a, b)$$$.

Изначально вся таблица пуста. Затем Алиса выполняет $$$q$$$ операций с коробкой для печенья. $$$i$$$-я операция ($$$1 \le i \le q$$$) выполняется следующим образом: указывается в настоящее время пустая клетка $$$(r_i,c_i)$$$ и форма (круг или квадрат), затем ставится печенье с предсказанием указанной формы в клетку $$$(r_i,c_i)$$$. Обратите внимание, что после $$$i$$$-й операции клетка $$$(r_i,c_i)$$$ больше не является пустой.

Перед всеми операциями и после каждой из $$$q$$$ операций Алиса задается вопросом, сколько существует способов разместить печенья с предсказанием во всех оставшихся пустых клетках, так чтобы было удовлетворено следующее требование:

Не существует трёх последовательных клеток с печеньем одинаковой формы в одной строке, одном столбце или на одной диагонали. Формально:

  • Не существует $$$(i,j)$$$, удовлетворяющих $$$1 \le i \le n, 1 \le j \le m-2$$$, таких, что в клетках $$$(i,j), (i,j+1), (i,j+2)$$$ есть печенье одинаковой формы.
  • Не существует $$$(i,j)$$$, удовлетворяющих $$$1 \le i \le n-2, 1 \le j \le m$$$, таких, что в клетках $$$(i,j), (i+1,j), (i+2,j)$$$ есть печенье одинаковой формы.
  • Не существует $$$(i,j)$$$, удовлетворяющих $$$1 \le i \le n-2, 1 \le j \le m-2$$$, таких, что в клетках $$$(i,j), (i+1,j+1), (i+2,j+2)$$$ есть печенье одинаковой формы.
  • Не существует $$$(i,j)$$$, удовлетворяющих $$$1 \le i \le n-2, 1 \le j \le m-2$$$, таких, что в клетках $$$(i,j+2), (i+1,j+1), (i+2,j)$$$ есть печенье одинаковой формы.

Все ответы должны быть выведены по модулю $$$998\,244\,353$$$. Также обратите внимание, что после некоторых операций требование уже может не быть удовлетворено с уже размещенными печеньями, в этом случае, вы должны выводить $$$0$$$.

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

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

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$, $$$q$$$ ($$$5 \le n, m \le 10^9, 0 \le q \le \min(n \times m, 10^5)$$$).

$$$i$$$-я из следующих $$$q$$$ строк содержит два целых числа $$$r_i$$$, $$$c_i$$$ и одну строку $$$\text{shape}_i$$$ ($$$1 \le r_i \le n, 1 \le c_i \le m$$$, $$$\text{shape}_i=$$$ «circle» или «square»), представляющих операции. Гарантируется, что клетка в $$$r_i$$$-й строке и $$$c_i$$$-м столбце изначально пуста. Это означает, что каждая $$$(r_i,c_i)$$$ появится не более одного раза в обновлениях.

Сумма $$$q$$$ по всем наборам входных данных теста не превышает $$$10^5$$$.

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

Для каждого набора входных данных выведите $$$q+1$$$ строк. Первая строка вывода должна содержать ответ до операций, $$$i$$$-я строка ($$$2 \le i \le q+1$$$) должна содержать ответ после первых $$$i-1$$$ операций. Все ответы должны быть взяты по модулю $$$998\,244\,353$$$.

Пример
Входные данные
2
6 7 4
3 3 circle
3 6 square
5 3 circle
5 4 square
5 5 3
1 1 circle
1 2 circle
1 3 circle
Выходные данные
8
4
3
1
0
8
4
1
0
Примечание

Во втором примере, после размещения печенья в форме круга в клетках $$$(1,1)$$$, $$$(1,2)$$$ и $$$(1,3)$$$, Требование уже не удовлетворено. Поэтому вы должны вывести $$$0$$$.