乌龟爱丽丝目前正在设计一个幸运饼干盒,她想将洛书的理论融入其中。
该框可以看作一个 $$$n \times m$$$ 网格 ($$$n, m \ge 5$$$),其中行编号为 $$$1, 2, \dots, n$$$,列编号为 $$$1, 2, \dots, m$$$。每个单元格可以是空的,也可以有一个以下形状之一的幸运饼干:圆形或方形。第 $$$a$$$ 行和第 $$$b$$$ 列交叉处的单元格表示为 $$$(a, b)$$$。
最初,整个网格是空的。然后,Alice 对幸运饼干盒执行 $$$q$$$ 操作。第 $$$i$$$ 操作 ($$$1 \le i \le q$$$) 如下:指定当前空单元格 $$$(r_i,c_i)$$$ 和形状(圆形或方形),然后将指定形状的幸运饼干放在单元格 $$$(r_i,c_i)$$$ 上。请注意,在第 $$$i$$$ 操作之后,单元格 $$$(r_i,c_i)$$$ 不再为空。
在所有操作之前和每次 $$$q$$$ 操作之后,Alice 想知道在所有剩余的空单元格中放置幸运饼干的方法有多少种,这样满足以下条件:
三个连续单元格(水平、垂直和两个对角线方向)均不包含相同形状的 cookie。正式:
- 不存在任何满足 $$$1 \le i \le n, 1 \le j \le m-2$$$ 的 $$$(i,j)$$$,使得单元格 $$$(i,j), (i,j+1), (i,j+2)$$$ 中存在相同形状的饼干。
- 不存在任何满足 $$$1 \le i \le n-2, 1 \le j \le m$$$ 的 $$$(i,j)$$$,使得单元格 $$$(i,j), (i+1,j), (i+2,j)$$$ 中存在相同形状的饼干。
- 不存在任何满足 $$$1 \le i \le n-2, 1 \le j \le m-2$$$ 的 $$$(i,j)$$$,使得单元格 $$$(i,j), (i+1,j+1), (i+2,j+2)$$$ 中存在相同形状的饼干。
- 不存在任何满足 $$$1 \le i \le n-2, 1 \le j \le m-2$$$ 的 $$$(i,j)$$$,使得单元格 $$$(i,j+2), (i+1,j+1), (i+2,j)$$$ 中存在相同形状的饼干。
您应该输出以 $$$998\,244\,353$$$ 为模的所有答案。另请注意,在某些操作之后,可能已经放置的糖果不满足条件,在这种情况下,您应该输出$$$0$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。
每个测试用例的第一行包含三个整数 $$$n$$$, $$$m$$$, $$$q$$$ ($$$5 \le n, m \le 10^9, 0 \le q \le \min(n \times m, 10^5)$$$)。
接下来的 $$$q$$$ 行中的第 $$$i$$$ 包含两个整数 $$$r_i$$$、$$$c_i$$$ 和一个字符串 $$$\text{shape}_i$$$ ($$$1 \le r_i \le n, 1 \le c_i \le m$$$, $$$\text{shape}_i=$$$ “圆”或“方”),代表运算。保证第 $$$r_i$$$ 行和第 $$$c_i$$$ 列上的单元格最初为空。这意味着每个 $$$(r_i,c_i)$$$ 在更新中最多出现一次。
所有测试用例的 $$$q$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出 $$$q+1$$$ 行。每个测试用例的第一行应包含任何操作之前的答案。第 $$$i$$$ 行 ($$$2 \le i \le q+1$$$) 应包含第一个 $$$i-1$$$ 操作后的答案。所有答案均应以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
2 6 7 4 3 3 circle 3 6 square 5 3 circle 5 4 square 5 5 3 1 1 circle 1 2 circle 1 3 circle
输出 #1
8 4 3 1 0 8 4 1 0
注意
在第二个示例中,将圆形幸运饼干放置到单元格 $$$(1,1)$$$、$$$(1,2)$$$ 和 $$$(1,3)$$$ 后,条件已不满足。因此,您应该输出$$$0$$$。