本題是 白噪音 的困難版本。

題目背景

我已啟動

題目描述

有一個由 $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$ 取模後的結果。

範例

輸入 1

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

輸出 1

0
1
120
8185
150994940
32990316
191006747
155490384
843115889

說明 1

對於第一組資料，由於兩人都無法選出對應大小的矩形，顯然不可能得到全部都不為白色的網格。

對於第二組資料，唯一可能的網格是

$$ \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)$ 互不相同。