CF1303F.Number of Components

You are given a matrix $n \times m$, initially filled with zeroes. We define $a_{i, j}$ as the element in the $i$-th row and the $j$-th column of the matrix.

Two cells of the matrix are connected if they share a side, and the elements in these cells are equal. Two cells of the matrix belong to the same connected component if there exists a sequence $s_1$, $s_2$, ..., $s_k$ such that $s_1$ is the first cell, $s_k$ is the second cell, and for every $i \in [1, k - 1]$, $s_i$ and $s_{i + 1}$ are connected.

You are given $q$ queries of the form $x_i$ $y_i$ $c_i$ ($i \in [1, q]$). For every such query, you have to do the following:

1. replace the element $a_{x, y}$ with $c$;
2. count the number of connected components in the matrix.

There is one additional constraint: for every $i \in [1, q - 1]$, $c_i \le c_{i + 1}$.

给你一个 $n \times m$ 的矩阵，初始时所有元素均为 $0$。我们用 $a_{i, j}$ 表示该矩阵第 $i$ 行、第 $j$ 列的元素。

若两个矩阵单元格具有公共边，且其中的元素值相等，则称这两个单元格是连通的。若存在一个序列 $s_1, s_2, \dots, 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. 统计当前矩阵中连通分量的总数。

另有一条附加约束：对每个 $i \in [1, q - 1]$，均有 $c_i \le c_{i + 1}$。

The first line contains three integers $n$, $m$ and $q$ ($1 \le n, m \le 300$, $1 \le q \le 2 \cdot 10^6$) — the number of rows, the number of columns and the number of queries, respectively.

Then $q$ lines follow, each representing a query. The $i$-th line contains three integers $x_i$, $y_i$ and $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)$). For every $i \in [1, q - 1]$, $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}$。

Print $q$ integers, the $i$-th of them should be equal to the number of components in the matrix after the first $i$ queries are performed.

输出 $q$ 个整数，其中第 $i$ 个整数应等于执行前 $i$ 个查询后矩阵中连通块的数量。