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

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.

见题面 Input 部分

见题面 Output 部分