说明

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

你将在这个棋盘上玩一个单人游戏。在一次操作中，你可以执行以下两种操作之一。

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

当无法再进行任何操作时，游戏结束。

棋盘会发生 $Q$ 次变动，每次变动会增加 $W$ 个筹码到第 $X$ 行第 $Y$ 列的格子上。在每次变动后，计算使用当前棋盘结束游戏所需的最少操作次数。

输入格式

第一行包含三个整数 $N$、$M$ 和 $Q$（$1 \leq N \leq 5$；$1 \leq M, Q \leq 100\;000$）。

接下来的 $N$ 行，每行包含 $M$ 个整数，表示 $A_{i,j}$（$0 \leq A_{i,j} \leq 100\;000$）。

接下来的 $Q$ 行，每行包含三个整数 $X$、$Y$ 和 $W$（$1 \leq X \leq N$；$1 \leq Y \leq M$；$1 \leq W \leq 10\;000$），表示一次棋盘变动。

输出格式

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

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

5
5

提示

样例 1 解释： 在第一次变动后，你可以按以下方式进行最少次数的操作。

• 在格子 $(1, 2)$ 上执行右移操作。
• 在格子 $(1, 2)$ 上执行下移操作。
• 在格子 $(2, 2)$ 上执行右移操作。
• 在格子 $(2, 2)$ 上执行右移操作。
• 在格子 $(1, 3)$ 上执行下移操作。

翻译由 DeepSeek V3.2 完成