У вас есть матрица размера $$$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}$$$.