У вас есть матрица размера \(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]\)). Для каждого такого запроса вам необходимо сделать следующее:
- заменить элемент \(a_{x, y}\) на \(c\);
- посчитать кол-во компонент связности в матрице.
Существует одно дополнительное ограничение: для каждого \(i \in [1, q - 1]\), \(c_i \le c_{i + 1}\).