题目描述

公元$1371$年，太祖下令在北极阁上大建庙宇，短短几年，鸡笼山上便建成了帝王庙、关公庙、真武庙、功臣庙、蒋王庙、都城隍庙、卞壶庙、忠烈庙、刘越王庙、曹武惠王庙共十座庙宇，统称为“十庙”。

后来，为了方便人们来鸡笼山进香礼佛，太祖下令疏通了鸡笼山下已淤塞多年的潮沟。于是，便有了“进香河”。

然而并不是所有人都可以来鸡笼山的，太祖在进香河上修建了一座石桥，中间悬挂了一块高$Rx$宽$Ry$的机关格图（如下图所示）。所有格子都是活动可翻转的，一面是白色，一面是黑色，这里我们用$0$表示白色，用$1$表示黑色。初始情况下，所有格子都是白色面朝前的。有$Rx+Ry$个机关按钮，对应$Rx$行和$Ry$列。一个按钮一旦触发，就会引发对应的一行或一列的格子同时翻转。

同时，善于识天象的谋臣刘基给出了一种黑白状态，称之为“厄运星”。每一位过往前去鸡笼山的人都需要触发且只触发一个按钮，触发后，如果来访者呈“厄运星”形状，则不允许通过。

每一天要来鸡笼山的人数$N$是事先就知道的，同时天朝神威浩荡，每一位来者一开始总是有很大概率触发编号为$1$的按钮，我们不妨用数列$A_1$,$A_2$,$\dots$,$A_N$来表示，问题保证了初始时候的$A$数列全为$1$。同时在整个问题中，$A_i$满足$1 \leq A_i \leq Rx+Ry$。太祖很关心那些不允许去鸡笼山的人数。于是他时不时就会询问关于“某一段时间内会有多少人不能通过“厄运星”的考验”。然而那些前来鸡笼山的文人墨客并不愿意如此单一的操作。来访者有可能会突然决定修改自己的触发按钮。更麻烦的情况，结伴而来的连续若干人会突然决定修改触发按钮并且都去触发同一个按钮。

现在这麻烦的问题交给了你。

输入格式

输入文件第一行有$2$个数字$Rx$和$Ry$表示机关格图的高和宽（如图所示）。之后$Rx$行每一行$Ry$个数字，描述了“厄运星”形状，每一个数字都满足非$0$即$1$。

之后一行有两个数字，分别为$N$和$M$，表示人数和询问修改的次数。

之后$M$行，对应$M$次询问或修改。每一行先有一个数字$t$：

若$t$为$0$：之后有$2$个数字$d$和$x$，表明将$A_d$修改为$x$。

若$t$为$1$：之后有$2$个数字$l$和$r$，表明询问第$l$个人到第$r$个人中有多少人触发按钮后会出现“厄运星”形状，从而无法通过。

若$t$为$2$：之后有$3$个数字$l$,$r$和$x$，表明将$A_l$,$A_{l+1}$,$\dots$,$A_{r-1}$,$A_r$都修改为$x$。

输出格式

对于每一次询问(即$t$为$1$的情况)，输出单独一行，一个整数描述了在区间$[l,r]$中满足要求的人数。

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

0
3

提示

对于$40\%$的数据，$N \leq 5000$,$M \leq 10000$。

存在$70\%$的数据，$N \leq 130000$,$M \leq 30000$。

对于$100\%$的数据，$N \leq 1000000$，$M \leq 120000$，$Rx \leq 2$，$Ry \leq 3$。