Grid Game: Non‐overlapping Attack Configurations

Consider an n × m grid game map where some cells may initially have obstacles. Each cell that is not an obstacle is a candidate to place a person (at most one person per cell). When a person is placed, you must assign them a facing direction (up, down, left, or right) and a positive integer "range". The range indicates the distance the person can attack. For example, if a person is at \((x,y)\) facing right and his range is set to 3, then he can attack up to cell \((x,y+3)\). However, note that a person’s attack cannot pass through obstacles – if an obstacle appears before reaching the designated range, the attack stops at the cell before the obstacle.

More formally, for any person placed at \((x,y)\) with a given direction, his effective attack range is defined as the contiguous set of cells in his facing direction starting from the cell immediately adjacent to \((x,y)\) and extending until (a) the number of cells equals the chosen range, or (b) an obstacle is encountered (in which case the attack range consists of the free cells before the obstacle). Different choices of the positive integer that yield the same set of attacked cells are considered identical.

There are two conditions to satisfy when placing one or more persons:

1. No person should be in the attack range of any other person.
2. The attack ranges of any two persons must be disjoint (this is to prevent wasting ammunition).

To order the persons for identification purposes, each cell in the grid is assigned a number according to its position: the cell at \((x,y)\) is numbered \((x-1)\times m + y\). For each person, consider the set of cells in his attack range and let the key for that person be the smallest numbered cell in his attack range. Then, after sorting all persons by this key in increasing order, assign them IDs in that order. Two placements are considered different if they differ in the number of persons placed, or there exists at least one person (with the same ID in the sorted order) whose effective attack range (i.e. the set of cell numbers that are attacked) differs.

UM has prepared 5 types of queries, where in each query some cells will be turned into obstacles (temporarily) and you are asked to count the number of valid placement configurations (as defined above) on the resulting grid. The queries are as follows:

1. Type 1: Set cell \((x,y)\) as an obstacle.
2. Type 2: Set all cells in row \(x\) as obstacles.
3. Type 3: Set all cells in column \(y\) as obstacles.
4. Type 4: Set a horizontal segment \((x,y), (x,y+1), \dots, (x,y+t)\) as obstacles.
5. Type 5: Set a vertical segment \((x,y), (x+1,y), \dots, (x+t,y)\) as obstacles.

Important: After each query, the grid is restored to its initial state.

You are required to compute the number of valid placements modulo \(998244353\).

Note: In this problem, every occurrence of \((x,y)\) in the statement denotes the point in the \(x^{th}\) row and \(y^{th}\) column.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) \((1 \leq n,m \leq \text{some limit},\ 1 \leq q \leq \text{some limit})\) representing the number of rows, columns, and queries respectively.

The next \(n\) lines each contain a string of length \(m\) consisting of characters. The character '0' denotes a free cell, and '1' denotes an obstacle.

Then, \(q\) lines follow. Each query has one of the following formats:

• Type 1: 1 x y
• Type 2: 2 x
• Type 3: 3 y
• Type 4: 4 x y t  (sets cells \((x,y)\) to \((x,y+t)\) as obstacles)
• Type 5: 5 x y t  (sets cells \((x,y)\) to \((x+t,y)\) as obstacles)

All indices are 1-indexed.

outputFormat

For each query, output a single integer – the number of valid placements modulo \(998244353\) after performing that query.

sample

2 2 2
00
00
1 1 1
2 2

1
1

</p>