Đây là phiên bản khó của bài toán White Noise.

Bối cảnh bài toán

Tôi đã khởi động

Mô tả bài toán

Cho một lưới kích thước $n \times m$ gồm $n \times m$ ô vuông đơn vị có cạnh bằng $1$. Mỗi ô vuông có một màu, ban đầu tất cả các ô đều là màu trắng.

Defect và Flaw thực hiện tô màu lưới theo một thứ tự tùy ý nhiều lần. Defect có thể chọn một vùng hình chữ nhật con kích thước $1 \times 2$ trong lưới và tô nó thành màu xanh đậm; Flaw có thể chọn một vùng hình chữ nhật con kích thước $1 \times 3$ và tô nó thành màu xanh nhạt.

Lưu ý rằng các hình chữ nhật mà hai người chọn có thể xoay. Nói cách khác, miễn là nằm trong phạm vi lưới, Defect có thể chọn hình chữ nhật $1$ hàng $2$ cột hoặc $2$ hàng $1$ cột; Flaw cũng tương tự. Ngoài ra, việc tô màu có thể chồng lấp lên nhau, nghĩa là không bắt buộc các ô được chọn phải đang là màu trắng.

Trong lưới cuối cùng, mỗi ô vuông phải là màu xanh đậm hoặc xanh nhạt, không được là màu trắng. Đặc biệt, có $k$ vị trí $(x_i, y_i)$ có các ràng buộc bổ sung, yêu cầu màu sắc tại đó phải là $c_i$, trong đó $c_i = 0$ biểu thị màu xanh đậm và $c_i = 1$ biểu thị màu xanh nhạt.

Bạn cần giúp Architect tính xem có bao nhiêu lưới cuối cùng khác nhau. Hai lưới được coi là khác nhau khi và chỉ khi tồn tại ít nhất một ô vuông tại cùng vị trí có màu sắc khác nhau, không phụ thuộc vào thứ tự thao tác và vị trí thao tác của Defect và Flaw. Vì kết quả có thể rất lớn, hãy lấy kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Bài toán này bao gồm nhiều bộ dữ liệu.

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $r, t$, lần lượt là số hiệu của subtask và số lượng bộ dữ liệu, trong đó bộ dữ liệu đầu tiên thỏa mãn $r=0$, các bộ còn lại có $r$ tương ứng với số hiệu subtask.

Tiếp theo là các bộ dữ liệu, với mỗi bộ dữ liệu:

• Dòng đầu tiên chứa ba số nguyên $n, m, k$, lần lượt là chiều dài, chiều rộng của lưới và số lượng ràng buộc bổ sung.
• $k$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $x_i, y_i, c_i$, biểu thị vị trí của ràng buộc thứ $i$ và màu sắc yêu cầu tại đó.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất là kết quả sau khi lấy modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

0
1
120
8185
150994940
32990316
191006747
155490384
843115889

Ghi chú

Đối với bộ dữ liệu đầu tiên, vì cả hai người đều không thể chọn được hình chữ nhật có kích thước tương ứng, nên rõ ràng không thể thu được lưới mà tất cả các ô đều không phải màu trắng.

Đối với bộ dữ liệu thứ hai, lưới duy nhất có thể thu được là

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

Giới hạn

Bài toán này sử dụng chấm điểm theo gói (bundled testing). Các giới hạn đặc biệt cho từng subtask như sau:

• Subtask 1 (10 điểm): $t \leq 100$, $n, m \leq 15$.
• Subtask 2 (30 điểm): $t \leq 10$, $n, m \leq 3\cdot 10^3$.
• Subtask 3 (30 điểm): $k = 0$.
• Subtask 4 (30 điểm): Không có giới hạn đặc biệt.

Đối với tất cả các dữ liệu, thỏa mãn:

• $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$;
• Các vị trí $(x_i, y_i)$ trong cùng một bộ dữ liệu là phân biệt.