F. Количество компонент
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть матрица размера $$$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]$$$). Для каждого такого запроса вам необходимо сделать следующее:

  1. заменить элемент $$$a_{x, y}$$$ на $$$c$$$;
  2. посчитать кол-во компонент связности в матрице.

Существует одно дополнительное ограничение: для каждого $$$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