Ce problème est la version difficile de Bruit blanc.

Contexte du problème

J'ai démarré

Énoncé

Il existe une grille de $n$ lignes et $m$ colonnes composée de $n \times m$ petits carrés de côté $1$. Chaque petit carré possède une couleur ; initialement, tous les carrés sont blancs.

Defect et Flaw effectuent des coloriages sur la grille dans un ordre arbitraire un certain nombre de fois. Defect peut choisir une sous-zone rectangulaire de taille $1 \times 2$ dans la grille et la colorier en bleu foncé ; Flaw peut choisir une sous-zone rectangulaire de taille $1 \times 3$ et la colorier en bleu clair.

Notez que les sous-rectangles choisis par les deux personnes peuvent être pivotés. En d'autres termes, tant que cela reste dans les limites de la grille, Defect peut choisir un rectangle de $1$ ligne et $2$ colonnes, ou de $2$ lignes et $1$ colonne ; il en va de même pour Flaw. De plus, les coloriages peuvent se chevaucher, c'est-à-dire qu'il n'est pas imposé que les sous-rectangles choisis soient initialement blancs.

Dans la grille finale, chaque petit carré doit être soit bleu foncé, soit bleu clair, sans aucun carré blanc restant. En particulier, il existe $k$ positions distinctes $(x_i, y_i)$ ayant des contraintes supplémentaires, exigeant que leur couleur soit $c_i$, où $c_i = 0$ représente le bleu foncé et $c_i = 1$ le bleu clair.

Vous devez aider l'Architecte à calculer combien de grilles finales différentes sont possibles. Deux grilles sont différentes si et seulement s'il existe au moins un petit carré à la même position ayant une couleur différente, indépendamment de l'ordre et des positions des opérations de Defect et Flaw. Comme la réponse peut être très grande, veuillez la calculer modulo $998\,244\,353$.

Entrée

Ce problème contient plusieurs jeux de données.

La première ligne de l'entrée contient deux entiers $r$ et $t$, représentant respectivement le numéro de la sous-tâche du cas de test et le nombre de jeux de données, où le premier exemple satisfait $r=0$ et les autres exemples correspondent aux numéros de sous-tâches associés.

Ensuite, chaque jeu de données est saisi successivement. Pour chaque jeu de données :

• La première ligne contient trois entiers $n, m, k$, représentant respectivement la longueur, la largeur de la grille et le nombre de contraintes supplémentaires.
• Dans les $k$ lignes suivantes, la $i$-ème ligne contient trois entiers $x_i, y_i, c_i$, représentant la position de la $i$-ème contrainte supplémentaire et la couleur requise.

Sortie

Pour chaque jeu de données, affichez un entier sur une ligne, représentant le résultat modulo $998\,244\,353$.

Exemples

Entrée 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

Sortie 1

0
1
120
8185
150994940
32990316
191006747
155490384
843115889

Remarque

Pour le premier jeu de données, comme aucun des deux ne peut choisir un rectangle de la taille correspondante, il est évidemment impossible d'obtenir une grille sans aucun carré blanc.

Pour le deuxième jeu de données, la seule grille possible est

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

Contraintes

Ce problème utilise des tests groupés. Les plages de données spécifiques pour chaque sous-tâche sont les suivantes :

• Sous-tâche 1 (10 points) : $t \leq 100$, $n, m \leq 15$.
• Sous-tâche 2 (30 points) : $t \leq 10$, $n, m \leq 3\cdot 10^3$.
• Sous-tâche 3 (30 points) : $k = 0$.
• Sous-tâche 4 (30 points) : Aucune contrainte particulière.

Pour toutes les données, les conditions suivantes sont satisfaites :

• $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$ ;
• Les $(x_i, y_i)$ au sein d'un même jeu de données sont tous distincts.