CF1933G.Turtle Magic: Royal Turtle Shell Pattern

Turtle Alice is currently designing a fortune cookie box, and she would like to incorporate the theory of LuoShu into it.

The box can be seen as an $n \times m$ grid ($n, m \ge 5$), where the rows are numbered $1, 2, \dots, n$ and columns are numbered $1, 2, \dots, m$. Each cell can either be empty or have a single fortune cookie of one of the following shapes: circle or square. The cell at the intersection of the $a$-th row and the $b$-th column is denoted as $(a, b)$.

Initially, the entire grid is empty. Then, Alice performs $q$ operations on the fortune cookie box. The $i$-th operation ($1 \le i \le q$) is as follows: specify a currently empty cell $(r_i,c_i)$ and a shape (circle or square), then put a fortune cookie of the specified shape on cell $(r_i,c_i)$. Note that after the $i$-th operation, the cell $(r_i,c_i)$ is no longer empty.

Before all operations and after each of the $q$ operations, Alice wonders what the number of ways to place fortune cookies in all remaining empty cells is, such that the following condition is satisfied:

No three consecutive cells (in horizontal, vertical, and both diagonal directions) contain cookies of the same shape. Formally:

• There does not exist any $(i,j)$ satisfying $1 \le i \le n, 1 \le j \le m-2$, such that there are cookies of the same shape in cells $(i,j), (i,j+1), (i,j+2)$.
• There does not exist any $(i,j)$ satisfying $1 \le i \le n-2, 1 \le j \le m$, such that there are cookies of the same shape in cells $(i,j), (i+1,j), (i+2,j)$.
• There does not exist any $(i,j)$ satisfying $1 \le i \le n-2, 1 \le j \le m-2$, such that there are cookies of the same shape in cells $(i,j), (i+1,j+1), (i+2,j+2)$.
• There does not exist any $(i,j)$ satisfying $1 \le i \le n-2, 1 \le j \le m-2$, such that there are cookies of the same shape in cells $(i,j+2), (i+1,j+1), (i+2,j)$.

You should output all answers modulo $998\,244\,353$. Also note that it is possible that after some operations, the condition is already not satisfied with the already placed candies, in this case you should output $0$.

海龟爱丽丝正在设计一款幸运饼干盒，并希望将洛书理论融入其中。

该盒子可视为一个 $n \times m$ 的网格（其中 $n, m \ge 5$），行编号为 $1, 2, \dots, n$，列编号为 $1, 2, \dots, m$。每个格子要么为空，要么放置一枚幸运饼干，其形状为圆形或方形之一。第 $a$ 行与第 $b$ 列交叉处的格子记为 $(a, b)$。

初始时，整个网格为空。随后，爱丽丝对幸运饼干盒执行 $q$ 次操作。第 $i$ 次操作（$1 \le i \le q$）如下：指定一个当前为空的格子 $(r_i,c_i)$ 和一种形状（圆形或方形），然后在格子 $(r_i,c_i)$ 上放置一枚指定形状的幸运饼干。注意，第 $i$ 次操作完成后，格子 $(r_i,c_i)$ 不再为空。

在所有操作开始前，以及每次操作结束后，爱丽丝都想知道：在所有剩余空格子中放置幸运饼干（每格至多一枚，形状为圆形或方形），使得以下条件成立的方案数是多少？

任意三个连续格子（水平、垂直及两个对角线方向）均不能同时包含同一种形状的饼干。形式化地：

• 不存在满足 $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$。

The first line of the input contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases.

The first line of each test case contains three integers $n$, $m$, $q$ ($5 \le n, m \le 10^9, 0 \le q \le \min(n \times m, 10^5)$).

The $i$-th of the next $q$ lines contains two integers $r_i$, $c_i$ and a single string $\text{shape}_i$ ($1 \le r_i \le n, 1 \le c_i \le m$, $\text{shape}_i=$ "circle" or "square"), representing the operations. It is guaranteed that the cell on the $r_i$-th row and the $c_i$-th column is initially empty. That means, each $(r_i,c_i)$ will appear at most once in the updates.

The sum of $q$ over all test cases does not exceed $10^5$.

输入的第一行包含一个整数 $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 =$ "circle" 或 "square"），表示一次操作。保证第 $r_i$ 行第 $c_i$ 列的格子初始为空，即每对 $(r_i,c_i)$ 在所有更新中至多出现一次。

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

For each test case, output $q+1$ lines. The first line of each test case should contain the answer before any operations. The $i$-th line ($2 \le i \le q+1$) should contain the answer after the first $i-1$ operations. All answers should be taken modulo $998\,244\,353$.

对于每个测试用例，输出 $q+1$ 行。每个测试用例的第一行应包含所有操作执行前的答案。第 $i$ 行（$2 \le i \le q+1$）应包含执行前 $i-1$ 次操作后的答案。所有答案均需对 $998\,244\,353$ 取模。

In the second sample, after placing a circle-shaped fortune cookie to cells $(1,1)$, $(1,2)$ and $(1,3)$, the condition is already not satisfied. Therefore, you should output $0$.

在第二个样例中，将圆形幸运饼干放置在单元格 $(1,1)$、$(1,2)$ 和 $(1,3)$ 后，条件已不再满足。因此，你应该输出 $0$。