Codeforces Round 929 (Div. 3) |
---|
Закончено |
Черепаха Алиса в настоящее время разрабатывает коробку для печенья с предсказаниями, и она хотела бы включить в нее теорию Лоушу.
Коробку можно рассматривать как таблицу размера $$$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$$$ операций Алиса задается вопросом, сколько существует способов разместить печенья с предсказанием во всех оставшихся пустых клетках, так чтобы было удовлетворено следующее требование:
Не существует трёх последовательных клеток с печеньем одинаковой формы в одной строке, одном столбце или на одной диагонали. Формально:
Все ответы должны быть выведены по модулю $$$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$$$.
26 7 43 3 circle3 6 square5 3 circle5 4 square5 5 31 1 circle1 2 circle1 3 circle
8 4 3 1 0 8 4 1 0
Во втором примере, после размещения печенья в форме круга в клетках $$$(1,1)$$$, $$$(1,2)$$$ и $$$(1,3)$$$, Требование уже не удовлетворено. Поэтому вы должны вывести $$$0$$$.
Название |
---|