Description

Given a grid graph with $n$ rows and $m$ columns, the top-left node is $(1, 1)$ and the bottom-right node is $(n, m)$. Each node is connected to its adjacent nodes (up, down, left, right, if they exist) by a weighted edge. Some edge weights are initially $1$.

A robot starts at the top-left corner and moves within the grid. The robot can move from a node to any adjacent node connected by an edge. Note that the robot can move freely as long as an edge exists between two nodes. The robot will not visit the same node twice, nor will it traverse the same edge twice. If the robot cannot make a valid move, it stops at its current node.

The robot has a built-in counter $r$, which is initially $r = 0$ at the top-left corner. Whenever the robot traverses an edge with weight $v$, the value of the counter $r$ becomes $\gcd(r, v)$. Here, $\gcd(0, a) = a$ is defined. If the robot reaches the bottom-right corner and $r \neq 1$, the robot will explode on the spot.

Since this robot is very precious, you do not want it to explode. You perform $q$ modification operations, each choosing an edge with weight $1$ and changing its weight. You hope that for all possible movement scenarios of the robot, it will not explode. However, this is not enough to guarantee the robot never explodes in any scenario. Therefore, for the initial state and after each modification, you want to know the minimum number of edges that need to be removed from the graph to ensure that for all possible movement scenarios, the robot will not explode—that is, there exists no path from the top-left to the bottom-right such that the final $r \neq 1$.

Input

The input is read from the file grid.in.

The first line contains four integers $n, m, q, c$.

The next $n$ lines each contain $m-1$ integers, where the $j$-th integer in the $i$-th line represents the weight of the edge $(i, j) - (i, j+1)$. Specifically, when $m=1$, this part will not appear, and the input proceeds to the next section.

The next $n-1$ lines each contain $m$ integers, where the $j$-th integer in the $i$-th line represents the weight of the edge $(i, j) - (i+1, j)$. Specifically, when $n=1$, this part will not appear, and the input proceeds to the next section.

The next $q$ lines each contain four integers $t, i, j, w$: $t = 1$ means modifying the weight of edge $(i, j) - (i, j+1)$ to $w$. $t = 2$ means modifying the weight of edge $(i, j) - (i+1, j)$ to $w$.

Note that $c=1$ indicates that the input is forced to be online. Specifically, when $c=1$, let lastans be the answer after the previous modification. For the first modification, lastans is the answer for the initial state. Then: When $t = 1$, the actual $i$ is $(i - 1 + \text{lastans}) \pmod n + 1$, and $j$ is $(j - 1 + \text{lastans}) \pmod{m-1} + 1$. When $t = 2$, the actual $i$ is $(i - 1 + \text{lastans}) \pmod{n-1} + 1$, and $j$ is $(j - 1 + \text{lastans}) \pmod m + 1$.

Note that the adjustment of the modification operation does not involve the weight $w$. It is guaranteed that only edges with weight $1$ are modified.

Output

Output to the file grid.out.

Output $q+1$ lines. The first line represents the answer without any modifications, and the following $q$ lines represent the answers after each modification.

Examples

Input 1

2 3 2 0
2 1
3 6
1 6 2
2 1 1 12
1 1 2 10

Output 1

1
1
2

Note 1

Initially, one can remove the edge from $(1, 2)$ to $(2, 2)$. The counter is $1$ for both paths the robot could take to reach the bottom-right corner.

After the first modification, one can remove the edge from $(2, 2)$ to $(2, 3)$. The counter is $1$ for both paths the robot could take to reach the bottom-right corner.

After the second modification, one can remove the edges from $(1, 1)$ to $(1, 2)$ and from $(2, 2)$ to $(2, 3)$. The counter is $1$ for the only path the robot could take to reach the bottom-right corner.

Note that this sample does not satisfy the constraints of any test cases. Even if it satisfies the data range, it will not appear in the test cases. You can use this sample for simple debugging.

Input 2

2 2 0 0
3
12
2 6

Output 2

2

Note 2

Initially, one can remove the edges from $(1, 1)$ to $(1, 2)$ and from $(2, 1)$ to $(2, 2)$. The robot cannot reach the bottom-right corner, so it will not explode.

Examples 3

See grid/grid3.in and grid/grid3.ans in the contestant directory. This sample satisfies the constraints of test cases $6 \sim 11$.

Examples 4

See grid/grid4.in and grid/grid4.ans in the contestant directory. This sample satisfies the constraints of test cases $16 \sim 20$.

Constraints

For all test data, it is guaranteed that $1 \le n, m \le 3 \times 10^5$, $2 \le n \times m \le 3 \times 10^5$, $0 \le q \le 3 \times 10^5$. For all initial and modified edge weights $w$, $1 \le w \le 10^9$.