题目名称：G. Turtle Magic: 皇家龟甲纹样

时间限制： 每个测试点 3 秒
内存限制： 256 MB

题目描述

乌龟爱丽丝正在设计一个幸运饼干盒，她希望将“洛书”理论融入其中。
这个盒子可以看作一个 $n \times m$ 的网格（$n, m \ge 5$），行编号为 $1, 2, \dots, n$，列编号为 $1, 2, \dots, m$。每个格子可以是空的，也可以放置一个形状为 圆形（circle） 或 方形（square） 的幸运饼干。
第 $a$ 行第 $b$ 列的格子记作 $(a, b)$。

初始时，整个网格是空的。然后爱丽丝会进行 $q$ 次操作。
第 $i$ 次操作（$1 \le i \le q$）如下：

• 指定一个当前为空的格子 $(r_i, c_i)$ 以及一个形状（圆形或方形）。
• 在该格子中放入一个指定形状的幸运饼干。
• 注意：操作后该格子不再是空的。

在所有操作之前以及每次操作之后，爱丽丝想知道：在剩余的所有空单元格中放置幸运饼干（每个空单元格放一个圆形或方形），有多少种放置方式，使得整个网格满足以下条件：

任意连续三个单元格（水平、垂直或两个对角线方向）不能出现相同形状的饼干。

具体地：

• 水平方向：不存在 $(i, j)$ 满足 $1 \le i \le n,\ 1 \le j \le m-2$，使得格子 $(i, j), (i, j+1), (i, j+2)$ 上的饼干形状相同。
• 垂直方向：不存在 $(i, j)$ 满足 $1 \le i \le n-2,\ 1 \le j \le m$，使得格子 $(i, j), (i+1, j), (i+2, j)$ 上的饼干形状相同。
• 主对角线方向（右下方向）：不存在 $(i, j)$ 满足 $1 \le i \le n-2,\ 1 \le j \le m-2$，使得格子 $(i, j), (i+1, j+1), (i+2, j+2)$ 上的饼干形状相同。
• 副对角线方向（左下方向）：不存在 $(i, j)$ 满足 $1 \le i \le n-2,\ 1 \le j \le m-2$，使得格子 $(i, j+2), (i+1, j+1), (i+2, j)$ 上的饼干形状相同。

你需要输出所有答案，对 $998244353$ 取模。
注意：如果某次操作后，已经放置的饼干就已经违反了上述条件（即存在三个连续相同形状的已放饼干），此时答案应为 $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$ 行，每行包含两个整数 $r_i, c_i$ 和一个字符串 $\text{shape}_i$（$1 \le r_i \le n, 1 \le c_i \le m$，$\text{shape}_i$ 为 "circle" 或 "square"），表示第 $i$ 次操作。
保证操作的格子 $(r_i, c_i)$ 在操作前是空的，即每个 $(r_i, c_i)$ 在同一个测试用例中最多出现一次。

所有测试用例的 $q$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出 $q+1$ 行：

• 第一行：在 任何操作之前 的答案。
• 第 $i$ 行（$2 \le i \le q+1$）：在 前 $i-1$ 次操作之后 的答案。
  所有答案对 $998244353$ 取模。

示例

输入：

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

输出：

8
4
3
1
0
8
4
1
0

示例解释
在第二个样例中，将圆形饼干放在 $(1,1), (1,2), (1,3)$ 后，水平方向出现三个连续圆形，违反了条件，因此输出 $0$。