White Noise

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

Ironclad and Silent paint the grid several times in some arbitrary order. Ironclad can choose a $1 \times 2$ sub-rectangle in the grid and paint it red; Silent can choose a $1 \times 3$ sub-rectangle in the grid and paint it green.

Note that the sub-rectangles chosen by both players can be rotated. In other words, as long as it fits within the grid, Ironclad can choose either a $1 \times 2$ or a $2 \times 1$ rectangle; the same applies to Silent. Furthermore, the painting 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 red or green, with no white squares remaining. 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 red and $c_i = 1$ denotes green.

You need to help Watcher calculate the number of different possible final grids. Two grids are considered different if and only if there is at least one square at the same position with a different color, regardless of the order and positions of the operations performed by Ironclad and Silent. 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, where the sample satisfies $r=0$.

For each test case:

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

Output

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

Examples

Input 1

0 9
1 0
2 2
1 1 0
2 2 0
3 2
1 2 1
2 3 1
4 3
1 2 1
2 2 0
3 3 0
6 5
2 2 1
4 1 1
3 2 1
6 3 0
1 1 1
7 0
9 2
5 8 1
4 8 1
14 1
7 3 0
15 3
5 8 1
9 2 0
7 11 0

Output 1

0
1
120
8185
150994940
32990316
191006747
155490384
843115889

Note

For the first test case, since neither player can select a rectangle of the required size, it is clearly 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 (13 points): $t \leq 10^4$, $n \leq 3$.
• Subtask 2 (11 points): $t \leq 100$, $n \leq 15$.
• Subtask 3 (25 points): $t \leq 50$, $n \leq 50$.
• Subtask 4 (16 points): $t \leq 10$, $n \leq 3\cdot 10^3$.
• Subtask 5 (22 points): $k = 0$.
• Subtask 6 (13 points): No special constraints.

For all test cases:

• $1 \leq t \leq 10^5$;
• $1 \leq n \leq 2\cdot 10^5$, $\sum n \leq 10^6$;
• $0 \leq k \leq \min(10^6, n^2)$, $\sum k \leq 2\cdot 10^6$;
• $1 \leq x_i, y_i \leq n$, $0 \leq c_i \leq 1$;
• All $(x_i, y_i)$ within the same test case are distinct.