大小为 $$$n \times m$$$ 的矩阵,其中每个单元包含 $$$0$$$ 或 $$$1$$$,如果大小为 $$$2 \times 2$$$ 的每个连续子矩阵中的总和恰好为 $$$2$$$,则被认为是漂亮的,即。 e.每个大小为 $$$2 \times 2$$$ 的“正方形”恰好包含两个 $$$1$$$ 和两个 $$$0$$$。
给定一个大小为 $$$n \times m$$$ 的矩阵。最初该矩阵的每个单元格都是空的。我们将第 $$$x$$$ 行和第 $$$y$$$ 列交叉处的单元格表示为 $$$(x, y)$$$。您必须处理三种类型的查询:
- $$$x$$$ $$$y$$$ $$$-1$$$ — 清除单元格 $$$(x, y)$$$(如果其中有数字);
- $$$x$$$ $$$y$$$ $$$0$$$ — 在单元格 $$$(x, y)$$$ 中写入数字 $$$0$$$,覆盖之前存在的数字(如果有);
- $$$x$$$ $$$y$$$ $$$1$$$ — 在单元格 $$$(x, y)$$$ 中写入数字 $$$1$$$,覆盖之前存在的数字(如果有)。
每次查询后,打印填充矩阵空单元格的方法数,以使结果矩阵美观。由于答案可能很大,请以 $$$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$$$ 为模。
示例
输入 #1
2 2 7 1 1 1 1 2 1 2 1 1 1 1 0 1 2 -1 2 1 -1 1 1 -1
输出 #1
3 1 0 1 2 3 6