给定一个矩阵 $$$n \times m$$$,最初用零填充。我们将 $$$a_{i, j}$$$ 定义为矩阵的第 $$$i$$$ 行和第 $$$j$$$ 列中的元素。
如果矩阵的两个单元共享一条边,则它们是相连的,并且这些单元中的元素相等。如果存在序列 $$$s_1$$$, $$$s_2$$$, ..., $$$s_k$$$,其中 $$$s_1$$$ 是第一个单元,$$$s_k$$$ 是第二个单元,并且对于每个 $$$i \in [1, k - 1]$$$、$$$s_i$$$ 和 $$$s_{i + ,则矩阵的两个单元属于同一连通分量1}$$$已连接。
您将获得 $$$q$$$ 形式的查询 $$$x_i$$$ $$$y_i$$$ $$$c_i$$$ ($$$i \in [1, q]$$$)。对于每个此类查询,您必须执行以下操作:
1. 将元素$$$a_{x, y}$$$替换为$$$c$$$;
2. 计算矩阵中连通分量的数量。
还有一个额外的约束:对于 [1, q - 1]$$$ 中的每个 $$$i \, $$$c_i \le c_{i + 1}$$$。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n, m \le 300$$$, $$$1 \le q \le 2 \cdot 10^6$$$) — 分别是行数、列数和查询数。
接下来是 $$$q$$$ 行,每行代表一个查询。第 $$$i$$$ 行包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$c_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$, $$$1 \le c_i \le \max(1000, \lceil \frac{2 \cdot 10^6}{nm} \rceil)$$$)。对于每个 $$$i \in [1, q - 1]$$$,$$$c_i \le c_{i + 1}$$$。
输出
打印 $$$q$$$ 整数,其中第 $$$i$$$ 应等于执行第一个 $$$i$$$ 查询后矩阵中的分量数。
示例
输入 #1
3 2 10 2 1 1 1 2 1 2 2 1 1 1 2 3 1 2 1 2 2 2 2 2 2 1 2 3 2 4 2 1 5
输出 #1
2 4 3 3 4 4 4 2 2 4