У вас есть матрица размера $$$n \times m$$$, изначально заполненная нулями. Элемент в $$$i$$$-й строке и $$$j$$$-м столбце обозначим как $$$a_{i, j}$$$.
Две ячейки матрицы являются связанными, если они имеют общую сторону, и элементы в этих ячейках равны. Две ячейки матрицы принадлежат одной и той же компоненте связности, если существует последовательность $$$s_1$$$, $$$s_2$$$, ..., $$$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]$$$). Для каждого такого запроса вам необходимо сделать следующее:
Существует одно дополнительное ограничение: для каждого $$$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}$$$.
Выведите $$$q$$$ целых чисел, $$$i$$$-е из них должно быть равно числу компонент связности в матрице после выполнения первых $$$i$$$ запросов.
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
Название |
---|