Данная задача является сложной версией задачи Белый шум.
Условие задачи
Я запустил процесс.
Имеется сетка размером $n \times m$, состоящая из $n \times m$ квадратов со стороной $1$. Каждый квадрат имеет определенный цвет; изначально все квадраты белые.
Defect и Flaw в некотором произвольном порядке раскрашивают сетку несколько раз. Defect может выбрать прямоугольную область размером $1 \times 2$ и закрасить её в темно-синий цвет; Flaw может выбрать прямоугольную область размером $1 \times 3$ и закрасить её в светло-синий цвет.
Заметьте, что выбранные прямоугольники можно поворачивать. Иными словами, если это позволяет размер сетки, Defect может выбрать как прямоугольник $1 \times 2$, так и $2 \times 1$; то же самое верно и для Flaw. Кроме того, раскрашивание может повторяться, то есть нет ограничений на то, что выбранные области должны быть изначально белыми.
В итоговой сетке каждый квадрат обязан быть либо темно-синим, либо светло-синим (белых квадратов быть не должно). В частности, для $k$ различных позиций $(x_i, y_i)$ заданы дополнительные ограничения: цвет в этих клетках должен быть равен $c_i$, где $c_i = 0$ означает темно-синий цвет, а $c_i = 1$ — светло-синий.
Вам нужно помочь Архитектору вычислить, сколько существует различных итоговых сеток. Две сетки считаются различными тогда и только тогда, когда существует хотя бы одна клетка с разными цветами, независимо от порядка и мест операций Defect и Flaw. Поскольку ответ может быть очень большим, выведите его по модулю $998\,244\,353$.
Входные данные
Задача содержит несколько наборов входных данных.
Первая строка содержит два целых числа $r$ и $t$, обозначающие номер подзадачи и количество наборов данных соответственно. Первый пример соответствует $r=0$, остальные соответствуют номерам подзадач.
Далее следуют $t$ наборов данных. Для каждого набора:
- Первая строка содержит три целых числа $n, m, k$, обозначающие размеры сетки и количество дополнительных ограничений.
- Следующие $k$ строк содержат по три целых числа $x_i, y_i, c_i$, обозначающие координаты $i$-го ограничения и требуемый цвет.
Выходные данные
Для каждого набора данных выведите одно целое число — количество способов по модулю $998\,244\,353$.
Примеры
Входные данные 1
0 1 1 1 0
Выходные данные 1
0
Примечание
Для первого набора данных, так как ни один из игроков не может выбрать прямоугольник нужного размера, очевидно, что невозможно получить сетку, в которой нет белых клеток.
Входные данные 2
0 1 2 2 2 1 1 0 2 2 0
Выходные данные 2
1
Примечание
Для второго набора данных единственно возможная сетка:
$$ \begin{bmatrix} 0 &0 \\ 0 &0\end{bmatrix}. $$
Ограничения
Задача использует пакетное тестирование. Ограничения для подзадач:
- Подзадача 1 (10 баллов): $t \leq 100$, $n, m \leq 15$.
- Подзадача 2 (30 баллов): $t \leq 10$, $n, m \leq 3\cdot 10^3$.
- Подзадача 3 (30 баллов): $k = 0$.
- Подзадача 4 (30 баллов): без дополнительных ограничений.
Для всех данных выполняются условия:
- $1 \leq t \leq 10^5$;
- $1 \leq n, m \leq 2\cdot 10^5$, $\sum {\color{blue}{\max(n, m)}} \leq 2\cdot 10^6$;
- $0 \leq k \leq \min(10^6, n\cdot m)$, $\sum k \leq 2\cdot 10^6$;
- $1 \leq x_i \leq n$, $1 \leq y_i \leq m$, $0 \leq c_i \leq 1$;
- Координаты $(x_i, y_i)$ внутри одного набора данных различны.