Este problema es la versión difícil de 白噪音.

Existe una cuadrícula de $n$ filas y $m$ columnas compuesta por $n \times m$ cuadrados unitarios. Cada cuadrado tiene un color; inicialmente, todos los cuadrados son blancos.

Defect y Flaw colorean la cuadrícula varias veces en un orden arbitrario. Defect puede elegir una subcuadrícula de tamaño $1 \times 2$ y pintarla de azul oscuro; Flaw puede elegir una subcuadrícula de tamaño $1 \times 3$ y pintarla de azul claro.

Tenga en cuenta que las subcuadrículas elegidas por ambos pueden rotarse. En otras palabras, siempre que estén dentro de los límites de la cuadrícula, Defect puede elegir un rectángulo de $1$ fila por $2$ columnas o de $2$ filas por $1$ columna; lo mismo aplica para Flaw. Además, las operaciones de ambos pueden solaparse, es decir, no hay restricción de que las subcuadrículas elegidas deban ser blancas.

En la cuadrícula final, cada cuadrado pequeño debe ser de color azul oscuro o azul claro, sin quedar ninguno blanco. En particular, existen $k$ posiciones distintas $(x_i, y_i)$ con restricciones adicionales, que requieren que su color sea $c_i$, donde $c_i = 0$ representa azul oscuro y $c_i = 1$ representa azul claro.

Usted debe ayudar al Architect a calcular cuántas cuadrículas finales distintas existen. Dos cuadrículas son diferentes si y solo si existe al menos una posición con un color distinto, independientemente del orden y la posición de las operaciones de Defect y Flaw. Dado que la respuesta puede ser muy grande, calcúlela módulo $998\,244\,353$.

Entrada

Este problema contiene múltiples casos de prueba.

La primera línea de la entrada contiene dos enteros $r$ y $t$, que representan el número de subtarea y el número de casos de prueba, respectivamente. El primer caso de ejemplo cumple $r=0$, y el resto de los casos cumplen con el número de subtarea correspondiente.

A continuación, se introducen los casos de prueba. Para cada caso:

• La primera línea contiene tres enteros $n, m, k$, que representan el largo, el ancho y el número de restricciones adicionales de la cuadrícula.
• Las siguientes $k$ líneas contienen tres enteros $x_i, y_i, c_i$, que representan la posición de la $i$-ésima restricción y el color requerido.

Salida

Para cada caso de prueba, imprima una línea con un entero que represente la respuesta módulo $998\,244\,353$.

Ejemplos

Entrada 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

Salida 1

0
1
120
8185
150994940
32990316
191006747
155490384
843115889

Nota

Para el primer caso, dado que ninguno de los dos puede elegir un rectángulo del tamaño correspondiente, es evidente que es imposible obtener una cuadrícula donde todos los cuadrados no sean blancos.

Para el segundo caso, la única cuadrícula posible es:

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

Restricciones

Este problema utiliza pruebas por lotes. Los rangos de datos para cada subtarea son los siguientes:

• Subtarea 1 (10 puntos): $t \leq 100$, $n, m \leq 15$.
• Subtarea 2 (30 puntos): $t \leq 10$, $n, m \leq 3\cdot 10^3$.
• Subtarea 3 (30 puntos): $k = 0$.
• Subtarea 4 (30 puntos): Sin restricciones especiales.

Para todos los datos, se cumple:

• $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$;
• Las posiciones $(x_i, y_i)$ dentro del mismo caso de prueba son distintas entre sí.