Задана матрица, состоящая из $$$n$$$ строк и $$$m$$$ столбцов.

Вы можете выполнять над ней два типа действий:

• покрасить весь столбец в синий;
• покрасить всю строку в красный.

Обратите внимание, что вы не можете выбирать, в какой цвет красить строку или столбец.

За одну секунду можно выполнить как одно действие, так и несколько одновременно. Если сделать одно действие, то это будет бесплатно. Если же сделать $$$k > 1$$$ действий одновременно, то на это придется потратить $$$k^2$$$ монет. Когда несколько действий выполняются одновременно, для каждой клетки, которая затрагивается действиями обоих типов, цвет можно выбрать независимо.

Требуется обработать $$$q$$$ запросов. Перед каждым запросом все ячейки становятся бесцветными. Изначально ограничений на итоговый цвет клеток нет. В $$$i$$$-м запросе добавляется ограничение вида:

• $$$x_i~y_i~c_i$$$ — клетка в строке $$$x_i$$$ в столбце $$$y_i$$$ должна быть покрашена в цвет $$$c_i$$$.

Таким образом, после $$$i$$$ запросов существует $$$i$$$ ограничений на необходимые цвета клеток матрицы. После каждого запроса выведите минимальную стоимость покраски в соответствии с ограничениями.