题目背景

What will tomorrow be? Or, what is tomorrow? Or, what was tomorrow......

What was yesterday? Or, what is yesterday? Or, what will yesterday be......

It is said that TIME cannot go back.

It is true, they all said.

Why? Are all those things inevitable? Is that really my unchangeable fate?

Where is the passion when we first met in that place?

I know that I messed it up, times and times again.

I want to turn back the clock and start again.

Yesterday Once More......

—— lgswdn

题目描述

注：题面中所有 $(x,y)$ 表示第 $x$ 行第 $y$ 列的点。

游戏的地图可以看成 $n\times m$ 的网格图。每个格子里可能会有障碍。对于每个非障碍格子，里面可以站人也可以不站人，当然，每个格子最多只能站一个人。

现在，你可以在非障碍点放置一些人，这些人都有一个朝向，这个朝向为上下左右中的一个。每个人你都可以给他设置他的射程，射程可以任意正整数。

射程：人攻击的距离；若一个人在 $(x,y)$，朝向向右，他的射程为 3，那么他最远可以攻击到 $(x,y+3)$。注意，一个人的攻击不能穿越障碍物。

现在，UM 想问问你整个游戏有多少种放人方法，使得所有人之间都不会互相攻击，而且任意两个人的攻击范围都不能有重叠（因为这样可能会浪费弹药），由于答案太大，所以 UM 要你给出答案对 $998244353$ 取模的结果。

我们设第 $x$ 行第 $y$ 列的格子编号为 $(x-1)\times m+y$，并把所有的人按他射程范围内的编号最小的格子的编号为关键字进行排序，并以排序后的顺序对所有人编号。两种放置人的情况被认为是不相同的，当且仅当两种情况人数不同或者存在一个编号相同的人射程范围内的格子中至少有一个格子编号不同。

但是，UM 觉得这个问题太简单了，会被强大的你两分钟切掉，于是，他为你精心准备了 5 种询问：
1、把点 $(x,y)$ 设置为障碍点后的放人方案数；
2、把第 $x$ 行整个设置为障碍后的放人方案数；
3、把第 $x$ 列整个设置为障碍后的放人方案数；
4、把点 $(x,y) ,\ (x,y+1),\dots,\ (x,y+t)$ 设置为障碍点后的放人方案数。
5、把点 $(x,y) ,\ (x+1,y),\dots,\ (x+t,y)$ 设置为障碍点后的放人方案数；

注意，每次操作后的地图都会还原成初始的状态。

输入格式

第一行两个正整数，$n,m$，意义如题面所述。

接下来 $n$ 行每行 $m$ 个整数，表示游戏地图。若这个数为 $1$ 则为非障碍点，若为 $0$ 则为障碍点。

接下来一行一个整数 $T$ 表示有 $T$ 个询问。

接下来 $T$ 行，每行的第一个整数 $opt$，表示这个询问的类型：
若 $opt=1$，则分别对应第一种询问，接下来输入两个正整数 $x,y$，意义如题面所述；
若 $opt=2,3$，则分别对应第二，三种询问，接下来输入一个整数 $x$，意义如题面所述；
若 $opt=4,5$，则分别对应第四，五种询问，接下来输入三个整数 $x,y,t$，意义如题面所述。

输出格式

输出共 $T+1$ 行。
第一行一个整数表示初始状态时的答案。
接下来 $T$ 行，一行一个整数表示每个询问的答案。

请注意：每个输出都应对 $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

提示

样例解释。

对于所有的询问，保证输入的参数均在棋盘大小范围内。

对于 $15\%$ 的数据，保证 $1<n,m\le 5$ 且 $1\le T\le 10$。
对于另外 $10\%$ 的数据，保证 $T=0$。
对于另外 $10\%$ 的数据，保证只有第 1 种询问。
对于另外 $15\%$ 的数据，保证只有第 2,3 种询问。
对于 $100\%$ 的数据，保证 $1<n\le m\le 15$，$0\le T\le 10^3$，第 1,4,5 种询问的总数不超过 $100$。

对于所有的数据，保证第 4,5 种询问中的 $t$ 为正整数。