People live in an $N \times K$ rectangular grid. Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left ($1 \le i \le N, 1 \le j \le K$). There are $N$ people living in the rectangular grid, where the $k$-th person lives in the cell $(k, 1)$.

In each cell, there is a weighted directed road to the cell immediately below it. That is, for all $i$ and $j$, one can move from $(i, j)$ to $(i+1, j)$ with a cost of $C_{i, j}$ ($1 \le i \le N-1, 1 \le j \le K$). Every month, all people move to the cells in the bottom row through these directed roads for a meeting.

However, the wicked wizard Pickle has modified the structure of the village to torment the people. Pickle chose two arrays $A$ and $B$ of size $N-1$, removed the roads from $(i, A_i)$ to $(i+1, A_i)$, and created roads from $(i, A_i)$ to $(i+1, B_i)$ ($1 \le i \le N-1$). The weight of the newly created road is the same as the weight of the removed road. Despite this, the poor people still move to the cells in the bottom row through the directed roads once a month.

Pickle is even capricious; before the people move, he chooses an $i$ and swaps $A_i$ and $B_i$ ($1 \le i \le N-1$).

Now, calculate the sum of the costs required for all people to move to the bottom row every time the wizard Pickle changes $A_i$ and $B_i$.

Input

The first line contains $N$ and $K$ separated by a space.

From the second line to the $N$-th line, the $(i+1)$-th line contains $C_{i, 1}, \ldots , C_{i, K}$ separated by spaces.

From the $(N+1)$-th line to the $(2N-1)$-th line, over $N-1$ lines, the $(i+N)$-th line contains $A_i$ and $B_i$ separated by a space.

The $(2N)$-th line contains the number of times $Q$ that Pickle changes $A_i$ and $B_i$.

From the $(2N+1)$-th line to the $(2N+Q)$-th line, the $(i+2N)$-th line contains $k, a, b$, which means Pickle changes $A_k$ to $a$ and $B_k$ to $b$.

($2 \le N \le 2 \times 10^5, 1 \le Q \le 2 \times 10^5, 1 \le K \le 10$, for all $i$, $1 \le A_i, B_i \le K$, for all $i, j$, $1 \le C_{i, j} \le 10^6$, for all queries, $1 \le k \le N-1, 1 \le a, b \le K$)

Output

The output consists of $Q$ lines in total.

The $i$-th line should contain the sum of the costs required for all people to move to the bottom row after the $i$-th time Pickle changes $A_k$ and $B_k$.

Subtasks

1. (5 points) $K=1$

2. (10 points) $N, Q \le 300$

3. (20 points) $N, Q \le 3000$

4. (10 points) $Q \le 100$

5. (55 points) No additional constraints.

Examples

Input 1

6 3
1 100 10000
1 100 10000
1 100 10000
1 100 10000
1 100 10000
3 1
1 2
2 1
1 3
1 1
4
1 2 3
2 3 2
5 1 3
2 1 1

Output 1

40209
40011
40011
40011