Problem - 1933G - Codeforces

Codeforces Round 929 (Div. 3)
Finished

→ Virtual participation

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests. If you've seen these problems, a virtual contest is not for you - solve these problems in the archive. If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive. Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

→ Problem tags

bitmasks

brute force

combinatorics

constructive algorithms

dfs and similar

math

*2300

No tag edit access

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 or have a single fortune cookie of one of the following shapes: or . 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 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=$ or ), 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$ .

Example

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

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