A11295. Turtle Magic: Royal Turtle Shell Pattern

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

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

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

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