你有一个大小为 $N \times M$ 的棋盘，行号从上到下编号为 $1$ 到 $N$，列号从左到右编号为 $1$ 到 $M$。初始时，第 $i$ 行第 $j$ 列的格子上有 $A_{i,j}$ 个筹码。

你将在该棋盘上进行单人游戏。在一次移动中，你可以执行以下操作之一：

• 选择一个不在最底行的格子，且该格子上至少有两个筹码。从该格子中移除一个筹码，并将另一个筹码移动到其正下方的格子中。
• 选择一个不在最右列的格子，且该格子上至少有一个筹码。将该格子上的一个筹码移动到其正右方的格子中。

当无法再进行任何移动时，游戏结束。

棋盘会有 $Q$ 次变更，每次变更都会在第 $X$ 行第 $Y$ 列的格子上增加 $W$ 个筹码。在每次变更后，请计算使游戏结束所需的最少移动次数。

输入格式

第一行包含三个整数 $N, M$ 和 $Q$ ($1 \le N \le 5; 1 \le M, Q \le 100\,000$)。接下来的 $N$ 行，每行包含 $M$ 个整数，表示 $A_{i,j}$ ($0 \le A_{i,j} \le 100\,000$)。接下来的 $Q$ 行，每行包含三个整数 $X, Y$ 和 $W$ ($1 \le X \le N; 1 \le Y \le M; 1 \le W \le 10\,000$)，表示对棋盘的一次变更。

输出格式

输出 $Q$ 行，每行包含一个整数，表示每次变更后使游戏结束所需的最少移动次数。

样例

输入 1

2 3 2
0 2 1
0 1 1
1 2 1
2 3 5

输出 1

5
5

说明 1

在第一次变更后，你可以按照以下方式进行游戏以达到最少移动次数：

1. 在格子 $(1, 2)$ 上向右移动。
2. 在格子 $(1, 2)$ 上向下移动。
3. 在格子 $(2, 2)$ 上向右移动。
4. 在格子 $(2, 2)$ 上向右移动。
5. 在格子 $(1, 3)$ 上向下移动。