← 返回题目列表

Codeforces · 1933/G

G. 海龟魔法:皇家龟壳图案

中文机器翻译题面 查看原题

乌龟爱丽丝目前正在设计一个幸运饼干盒,她想将洛书的理论融入其中。

该框可以看作一个 $$$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$$$。