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

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