E. Раскраска
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Матрица размера $$$n \times m$$$, состоящая только из цифр $$$0$$$ или $$$1$$$ считается красивой, если сумма в каждой подматрице размера $$$2 \times 2$$$ ровно $$$2$$$, т. е. каждый «квадрат» размера $$$2 \times 2$$$ содержит ровно две цифры $$$1$$$ и две цифры $$$0$$$.

Вам задана матрица размера $$$n \times m$$$. Изначально все ячейки матрицы пусты. Обозначим ячейку стоящую на пересечении $$$x$$$-й строки $$$y$$$-го столбца как $$$(x, y)$$$. Вам нужно обрабатывать запросы трех типов:

  • $$$x$$$ $$$y$$$ $$$-1$$$ — сделать ячейку $$$(x, y)$$$ пустой;
  • $$$x$$$ $$$y$$$ $$$0$$$ — записать цифру $$$0$$$ в ячейку $$$(x, y)$$$, это перезапишет то, что там было;
  • $$$x$$$ $$$y$$$ $$$1$$$ — записать цифру $$$1$$$ в ячейку $$$(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