Description

Note: In the statement, all $(x,y)$ refer to the cell in row $x$ and column $y$.

The game map can be seen as an $n\times m$ grid. Each cell may contain an obstacle. For each non-obstacle cell, it may contain a person or not; of course, each cell can contain at most one person.

Now, you can place some people on non-obstacle cells. Each person has a direction, which is one of up, down, left, or right. For each person, you can set their attack range, and the range can be any positive integer.

Attack range: the distance a person can attack. If a person is at $(x,y)$, facing right, and their range is 3, then the farthest cell they can attack is $(x,y+3)$. Note that a person’s attack cannot pass through obstacles.

Now UM wants to ask: how many ways are there to place people on the whole map such that no two people can attack each other, and the attack ranges of any two people cannot overlap (because that may waste bullets). Since the answer is too large, you need to output the result modulo $998244353$.

We number the cell in row $x$ and column $y$ as $(x-1)\times m+y$. For all people, sort them by the number of the cell with the smallest number within their attack range, and then assign IDs to all people in this sorted order. Two placements are considered different if and only if the number of people is different, or there exists a person with the same ID such that among the cells in their attack range, at least one cell number is different.

However, UM thinks this problem is too easy and might be solved by powerful you in two minutes, so he carefully prepared 5 types of queries for you:

1. The number of placements after setting cell $(x,y)$ as an obstacle.
2. The number of placements after setting the entire row $x$ as obstacles.
3. The number of placements after setting the entire column $x$ as obstacles.
4. The number of placements after setting cells $(x,y) ,\ (x,y+1),\dots,\ (x,y+t)$ as obstacles.
5. The number of placements after setting cells $(x,y) ,\ (x+1,y),\dots,\ (x+t,y)$ as obstacles.

Note: After each operation, the map will be restored to the initial state.

Input Format

The first line contains two positive integers $n,m$, with the meaning as described in the statement.

The next $n$ lines each contain $m$ integers, describing the game map. If the number is $1$, the cell is non-obstacle; if the number is $0$, the cell is an obstacle.

The next line contains an integer $T$, meaning there are $T$ queries.

The next $T$ lines: the first integer of each line is $opt$, meaning the type of this query:
If $opt=1$, it corresponds to the first type of query, followed by two positive integers $x,y$, with the meaning as described in the statement.
If $opt=2,3$, they correspond to the second and third types of queries, followed by one integer $x$, with the meaning as described in the statement.
If $opt=4,5$, they correspond to the fourth and fifth types of queries, followed by three integers $x,y,t$, with the meaning as described in the statement.

Output Format

Output a total of $T+1$ lines.
The first line contains one integer, the answer for the initial state.
The next $T$ lines each contain one integer, the answer for each query.

Note: Each output should be taken modulo $998244353$.

3 3
0 1 0
1 1 1
0 1 0
5
1 2 2
2 2
3 1
4 2 1 1
5 2 2 1

7
1
1
5
1
1

4 4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
3
2 4
1 2 2
4 3 2 2

400
60
400
144

Hint

Sample explanation。

For all queries, it is guaranteed that the input parameters are within the board size.

For $15\%$ of the testdata, it is guaranteed that $1<n,m\le 5$ and $1\le T\le 10$.
For another $10\%$ of the testdata, it is guaranteed that $T=0$.
For another $10\%$ of the testdata, it is guaranteed that only the first type of query exists.
For another $15\%$ of the testdata, it is guaranteed that only the second and third types of queries exist.
For $100\%$ of the testdata, it is guaranteed that $1<n\le m\le 15$, $0\le T\le 10^3$, and the total number of queries of types 1, 4, and 5 does not exceed $100$.

For all testdata, it is guaranteed that in queries of types 4 and 5, $t$ is a positive integer.

Translated by ChatGPT 5