在一个 $N \times K$ 的矩形网格中住着一些人。 我们将从上往下第 $i$ 行、从左往右第 $j$ 列的格子记作 $(i, j)$（$1 \le i \le N, 1 \le j \le K$）。 网格中住着 $N$ 个人，第 $k$ 个人住在 $(k, 1)$ 格子中。

每个格子都有通往其下方相邻格子的带权单向道路。 即对于所有的 $i, j$，从 $(i, j)$ 到 $(i+1, j)$ 的移动代价为 $C_{i, j}$（$1 \le i \le N-1, 1 \le j \le K$）。 所有人每个月都要通过这些单向道路移动到最底行（第 $N$ 行）的某个格子中。

然而，邪恶的魔法师 Pickle 为了折磨人们，施展魔法改变了村庄的结构。 Pickle 定义了两个长度为 $N-1$ 的数组 $A$ 和 $B$，他移除了从 $(i, A_i)$ 到 $(i+1, A_i)$ 的道路，并新建了一条从 $(i, A_i)$ 到 $(i+1, B_i)$ 的道路（$1 \le i \le N-1$）。 新建道路的权重与被移除道路的权重相同。 尽管如此，可怜的人们每个月仍然需要通过这些单向道路移动到最底行。

甚至，Pickle 还非常反复无常，在人们移动之前，他会选择一个 $i$ 并修改 $A_i$ 和 $B_i$（$1 \le i \le N-1$）。

现在，请计算每当魔法师 Pickle 修改 $A_i$ 和 $B_i$ 后，所有人移动到最底行所需代价的总和。

输入格式

第一行包含两个整数 $N$ 和 $K$，中间用空格隔开。

从第二行到第 $N$ 行，第 $(i+1)$ 行包含 $C_{i, 1}, \ldots , C_{i, K}$，中间用空格隔开。

从第 $N+1$ 行到第 $2N-1$ 行，共 $N-1$ 行，第 $(i+N)$ 行包含 $A_i$ 和 $B_i$，中间用空格隔开。

第 $2N$ 行包含 Pickle 修改 $A_i$ 和 $B_i$ 的次数 $Q$。

从第 $2N+1$ 行到第 $2N+Q$ 行，第 $(i+2N)$ 行包含 $k, a, b$，表示 Pickle 将 $A_k$ 修改为 $a$，将 $B_k$ 修改为 $b$。

（$2 \le N \le 2 \times 10^5, 1 \le Q \le 2 \times 10^5, 1 \le K \le 10$，对于所有 $i$，$1 \le A_i, B_i \le K$，对于所有 $i, j$，$1 \le C_{i, j} \le 10^6$，对于所有查询，$1 \le k \le N-1, 1 \le a, b \le K$）

输出格式

输出共 $Q$ 行。

第 $i$ 行输出第 $i$ 次 Pickle 修改 $A_k, B_k$ 后，所有人移动到最底行所需代价的总和。

子任务

1. (5分) $K=1$

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

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

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

5. (55分) 无额外限制。

样例

输入 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

输出 1

40209
40011
40011
40011