Матрица размера \(n \times m\), состоящая только из цифр \(0\) или \(1\) считается красивой, если сумма в каждой подматрице размера \(2 \times 2\) ровно \(2\), т. е. каждый «квадрат» размера \(2 \times 2\) содержит ровно две цифры \(1\) и две цифры \(0\).
Вам задана матрица размера \(n \times m\). Изначально все ячейки матрицы пусты. Обозначим ячейку стоящую на пересечении \(x\)-й строки \(y\)-го столбца как \((x, y)\). Вам нужно обрабатывать запросы трех типов:
После каждого запроса выведите количество способов заполнить пустые ячейки матрицы так, чтобы матрица была красивой. Так как это значение может быть слишком велико, выведите его по модулю \(998244353\).
Первая строка содержит три числа \(n\), \(m\) и \(k\) (\(2 \le n, m \le 10^6\); \(1 \le k \le 3 \cdot 10^5\)) — количество строк матрицы, количество столбцов и количество запросов соответственно.
Следующие \(k\) строк содержат описания запросов. \(i\)-я строка содержит три числа \(x_i\), \(y_i\), \(t_i\) (\(1 \le x_i \le n\); \(1 \le y_i \le m\); \(-1 \le t_i \le 1\)) — параметры \(i\)-го запроса.
После каждого запроса выведите число — количество способов заполнить пустые ячейки матрицы так, чтобы матрица была красивой по модулю \(998244353\).
2 2 7 1 1 1 1 2 1 2 1 1 1 1 0 1 2 -1 2 1 -1 1 1 -1
3 1 0 1 2 3 6
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач