白噪音+

• 时间限制：$4$ 秒
• 空间限制：$512\text{ MB}$

本题是 白噪音 的困难版本。

题目背景

我已启动

题目描述

有一个由 $n \times m$ 个边长为 $1$ 的小正方形拼接而成的 $n$ 行 $m$ 列网格。每个小正方形有一种颜色，初始时，所有正方形都是白色。

Defect 和 Flaw 按某种任意顺序 在网格内涂色若干次。Defect 可以选择网格中一个大小为 $1 \times 2$ 的子矩形区域，并将其涂为深蓝色；Flaw 可以选择网格中一个大小为 $1\times 3$ 的子矩形区域，并将其涂为浅蓝色。

注意，两人选择的子矩形 可以旋转。换句话说，只要在网格范围内，Defect 既可以选择 $1$ 行 $2$ 列的矩形，也可以选择 $2$ 行 $1$ 列的矩形；Flaw 同理。此外，两人的涂色可以重复，也就是不限制所选择的子矩形区域必须均为白色。

最终的网格里，每个小正方形 必须 为深蓝色或浅蓝色之一，不包括白色。特别地，有 $k$ 个不同的位置 $(x_i, y_i)$ 有额外限制，要求其颜色必须为 $c_i$，其中 $c_i = 0$ 表示深蓝色，$c_i = 1$ 表示浅蓝色。

你需要帮助 Architect 计算共有多少种不同的最终网格。两种网格不同，当且仅当存在至少一个相同位置的小正方形颜色不同，而与 Defect 和 Flaw 的操作顺序及操作位置无关。由于答案可能很大，请对 $998\,244\,353$ 取模。

输入格式

本题包含多组测试数据。

输入第一行包含两个整数 $r, t$，分别表示测试点所在的子任务编号和测试数据组数，其中第一组样例满足 $r=0$，其余样例的 $r$ 符合对应的子任务标号。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含三个整数 $n, m, k$，分别表示网格的长、宽与额外限制的数量。
• 接下来 $k$ 行中第 $i$ 行包含三个整数 $x_i, y_i, c_i$，分别表示第 $i$ 个额外要求的位置与其要求的颜色。

输出格式

对于每组测试数据，输出一行一个整数，表示答案对 $998\,244\,353$ 取模后的结果。

样例输入

0 8
1 1 0
2 2 2
1 1 0
2 2 0
3 3 2
1 2 1
2 3 1
4 4 3
1 2 1
2 2 0
3 3 0
2 6 2
2 5 1
1 3 0
7 4 4
1 3 1
2 2 1
6 4 1
7 4 0
14 13 0
5 19 0

样例输出

0
1
120
8185
150994940
32990316
191006747
155490384
843115889

样例解释

对于第一组数据，由于两人都无法选出对应大小的矩形，显然不可能得到全部都不为白色的网格。

对于第二组数据，唯一可能的网格是

$$ \begin{bmatrix} 0 &0 \\ 0 &0\end{bmatrix}. $$

数据规模与约定

本题使用捆绑测试。 各个子任务对应的特殊数据范围如下：

• Subtask 1（10 分）：$t \leq 100$，$n, m \leq 15$。
• Subtask 2（30 分）：$t \leq 10$，$n, m \leq 3\cdot 10^3$。
• Subtask 3（30 分）：$k = 0$。
• Subtask 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)$ 互不相同。