This problem is the hard version of White Noise.

Background

I have initiated.

Description

There is an $n \times m$ grid composed of $n \times m$ unit squares, each with a side length of $1$. Each square has a color; initially, all squares are white.

Defect and Flaw color the grid several times in some arbitrary order. Defect can choose a $1 \times 2$ sub-rectangle in the grid and color it dark blue; Flaw can choose a $1 \times 3$ sub-rectangle and color it light blue.

Note that the sub-rectangles chosen by both can be rotated. In other words, as long as it is within the grid boundaries, Defect can choose either a $1 \times 2$ or a $2 \times 1$ rectangle; the same applies to Flaw. Furthermore, their coloring operations can overlap, meaning there is no restriction that the chosen sub-rectangles must be white.

In the final grid, every unit square must be either dark blue or light blue; no white squares are allowed. Specifically, there are $k$ distinct positions $(x_i, y_i)$ with additional constraints, requiring their color to be $c_i$, where $c_i = 0$ denotes dark blue and $c_i = 1$ denotes light blue.

You need to help Architect calculate the total number of different final grids. Two grids are different if and only if there exists at least one square at the same position with a different color, regardless of the order or positions of Defect's and Flaw's operations. Since the answer may be very large, output it modulo $998\,244\,353$.

Input

The input contains multiple test cases.

The first line contains two integers $r$ and $t$, representing the subtask ID and the number of test cases, respectively. The first sample satisfies $r=0$, and the remaining samples satisfy $r$ corresponding to their subtask IDs.

For each test case:

• The first line contains three integers $n, m, k$, representing the length, width, and the number of additional constraints of the grid.
• Each of the next $k$ lines contains three integers $x_i, y_i, c_i$, representing the position and the required color of the $i$-th constraint.

Output

For each test case, output a single integer representing the answer modulo $998\,244\,353$.

Examples

Input 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

Output 1

0
1
120
8185
150994940
32990316
191006747
155490384
843115889

Note

For the first test case, since neither person can select a rectangle of the required size, it is impossible to obtain a grid where no squares are white.

For the second test case, the only possible grid is:

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

Constraints

This problem uses bundled testing. The specific data ranges for each subtask are as follows:

• Subtask 1 (10 points): $t \leq 100$, $n, m \leq 15$.
• Subtask 2 (30 points): $t \leq 10$, $n, m \leq 3\cdot 10^3$.
• Subtask 3 (30 points): $k = 0$.
• Subtask 4 (30 points): No special constraints.

For all data, it is satisfied that:

• $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$;
• All $(x_i, y_i)$ within the same test case are distinct.