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

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.