给定一个大小为 $n\times m$ 的网格图 $G=(V,E)$，边有边权。

定义该图的一个生成子图 $G'=(V,E')$ 是合法的，当且仅当任意一条（不存在也合法）从 $(1,1)$ 到 $(n,m)$ 的路径上边权的 $\gcd$ 均为 $1$。

特别的，共有 $q$ 次修改操作，每次修改一条边的边权，保证修改前该条边的边权为 $1$。求每次操作后的合法生成子图的 $|E|-|E'|_{\max}$，本题强制在线。

$1\leq n\times m\leq 3\times 10^5,1\leq q\leq 3\times10^5,1\leq V\leq 10^9$。其中 $V$ 表示边权的最大值。

输入格式

第一行 $n,m,q,c$

下面 $n$ 行，每行 $m-1$ 个，为 $(i,j)$ 到 $(i,j+1)$ 的边。

下面 $n-1$ 行，每行 $m$ 个，为 $(i,j)$ 到 $(i+1,j)$ 的边。

之后 $q$ 行每行 $t,x,y,w$，若 $t=1$ 改 $(x,y)$ 与 $(x,y+1)$ 边，否则改 $(x,y)$ 与 $(x+1,y)$ 边。若 $c=1$ 需要 将 $x$ 和 $y$ 在合法范围内向右循环移位（取模）。

输出格式

$q+1$ 行，为询问前和 $q$ 次询问后的答案。

input

3 3 5 0
1 1
899179204 812728620
460831140 767051180
1 1 1
814278220 248850028 194211270
2 1 2 507466885
2 1 3 631331232
1 1 1 344408526
2 1 1 941451115
1 1 2 165876708

output

0
0
0
0
1
2