Niniejsze zadanie jest trudniejszą wersją zadania Biały szum.

Uruchomiono

Mamy siatkę o wymiarach $n \times m$ złożoną z $n \times m$ kwadratów o boku $1$. Każdy kwadrat ma określony kolor; początkowo wszystkie kwadraty są białe.

Defect i Flaw malują siatkę w dowolnej kolejności wielokrotnie. Defect może wybrać podprostokąt o wymiarach $1 \times 2$ i pomalować go na ciemnoniebiesko; Flaw może wybrać podprostokąt o wymiarach $1 \times 3$ i pomalować go na jasnoniebiesko.

Zauważ, że wybrane przez nich podprostokąty mogą być obracane. Innymi słowy, o ile mieszczą się w granicach siatki, Defect może wybrać prostokąt o wymiarach $1$ wiersz na $2$ kolumny lub $2$ wiersze na $1$ kolumnę; to samo dotyczy Flawa. Ponadto malowanie może się nakładać, co oznacza, że nie ma ograniczenia, według którego wybrane obszary muszą być początkowo białe.

W końcowej siatce każdy kwadrat musi mieć kolor ciemnoniebieski lub jasnoniebieski (nie może być biały). W szczególności istnieje $k$ różnych pozycji $(x_i, y_i)$, dla których nałożono dodatkowe ograniczenia: wymagają one, aby kolor w tym miejscu wynosił $c_i$, gdzie $c_i = 0$ oznacza kolor ciemnoniebieski, a $c_i = 1$ oznacza kolor jasnoniebieski.

Pomóż Architectowi obliczyć, ile istnieje różnych możliwych siatek końcowych. Dwie siatki są różne wtedy i tylko wtedy, gdy istnieje co najmniej jedno pole o innym kolorze; kolejność operacji oraz miejsca wykonania operacji przez Defecta i Flawa nie mają znaczenia. Ponieważ wynik może być bardzo duży, należy go podać modulo $998\,244\,353$.

Wejście

Zadanie zawiera wiele zestawów danych testowych.

Pierwsza linia wejścia zawiera dwie liczby całkowite $r$ oraz $t$, oznaczające odpowiednio numer podzadania oraz liczbę zestawów danych testowych. Pierwszy zestaw przykładów spełnia $r=0$, a pozostałe zestawy spełniają $r$ zgodnie z numeracją podzadań.

Dla każdego zestawu danych:

• Pierwsza linia zawiera trzy liczby całkowite $n, m, k$, oznaczające odpowiednio wysokość siatki, szerokość siatki oraz liczbę dodatkowych ograniczeń.
• Każda z kolejnych $k$ linii zawiera trzy liczby całkowite $x_i, y_i, c_i$, oznaczające odpowiednio współrzędne $i$-tego wymaganego pola oraz wymagany kolor.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii liczbę sposobów modulo $998\,244\,353$.

Przykład

Wejście 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

Wyjście 1

0
1
120
8185
150994940
32990316
191006747
155490384
843115889

Uwagi

Dla pierwszego zestawu danych, ponieważ żadna z osób nie może wybrać prostokąta o odpowiednim rozmiarze, uzyskanie siatki bez białych pól jest niemożliwe.

Dla drugiego zestawu danych jedyną możliwą siatką jest

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

Ograniczenia

Zadanie wykorzystuje testowanie wiązkowe. Szczegóły dotyczące podzadań:

• Podzadanie 1 (10 pkt): $t \leq 100$, $n, m \leq 15$.
• Podzadanie 2 (30 pkt): $t \leq 10$, $n, m \leq 3\cdot 10^3$.
• Podzadanie 3 (30 pkt): $k = 0$.
• Podzadanie 4 (30 pkt): brak dodatkowych ograniczeń.

Dla wszystkich danych wejściowych spełnione są warunki:

• $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$;
• Współrzędne $(x_i, y_i)$ wewnątrz jednego zestawu danych są parami różne.