A13184. 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}$ .

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}$ .

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.