You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in c++17.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```cpp
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
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 Format
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 Format
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$$$.

## Examples
```input
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$$$.

Now solve the problem and return the code.