Number of Components
Description
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:
- replace the element $a_{x, y}$ with $c$;
- 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.
Input
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}$.
Output
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.
Samples
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
2
4
3
3
4
4
4
2
2
4