311099: CF1933G. Turtle Magic: Royal Turtle Shell Pattern

G. Turtle Magic: Royal Turtle Shell Patterntime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$.

Input

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$.

Output

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$.

ExampleInput

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

Output

8
4
3
1
0
8
4
1
0

Note

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$.

题目大意：
Turtle Alice正在设计一个幸运饼干盒，并希望将洛书理论融入其中。盒子的模型是一个\( n \times m \)的网格（\( n, m \ge 5 \)），行从1到\( n \)编号，列从1到\( m \)编号。每个单元格要么是空的，要么包含一个圆形或方形幸运饼干。网格的初始状态是全空。Alice会对饼干盒执行\( q \)个操作，每次操作在一个空单元格中放置一个指定形状的幸运饼干。在所有操作之前以及每次操作之后，Alice想知道在所有剩余的空单元格中放置幸运饼干的方式数，使得没有任何三个连续的单元格（水平、垂直和两个对角线方向）包含相同形状的饼干。

输入输出数据格式：
输入：
- 第一行包含一个整数\( 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"），代表操作。
- 所有测试用例中\( q \)的总和不超过\( 10^5 \)。

输出：
- 对于每个测试用例，输出\( q+1 \)行。每个测试用例的第一行是在任何操作之前答案，第\( i \)行（\( 2 \le i \le q+1 \)）是在前\( i-1 \)次操作之后的答案。
- 所有答案都应该对\( 998\,244\,353 \)取模。

注意：在某个操作之后，如果已经放置的饼干使得条件不再满足，应该输出0。题目大意： Turtle Alice正在设计一个幸运饼干盒，并希望将洛书理论融入其中。盒子的模型是一个\( n \times m \)的网格（\( n, m \ge 5 \)），行从1到\( n \)编号，列从1到\( m \)编号。每个单元格要么是空的，要么包含一个圆形或方形幸运饼干。网格的初始状态是全空。Alice会对饼干盒执行\( q \)个操作，每次操作在一个空单元格中放置一个指定形状的幸运饼干。在所有操作之前以及每次操作之后，Alice想知道在所有剩余的空单元格中放置幸运饼干的方式数，使得没有任何三个连续的单元格（水平、垂直和两个对角线方向）包含相同形状的饼干。 输入输出数据格式： 输入： - 第一行包含一个整数\( 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"），代表操作。 - 所有测试用例中\( q \)的总和不超过\( 10^5 \)。 输出： - 对于每个测试用例，输出\( q+1 \)行。每个测试用例的第一行是在任何操作之前答案，第\( i \)行（\( 2 \le i \le q+1 \)）是在前\( i-1 \)次操作之后的答案。 - 所有答案都应该对\( 998\,244\,353 \)取模。 注意：在某个操作之后，如果已经放置的饼干使得条件不再满足，应该输出0。