Задана матрица, состоящая из \(n\) строк и \(m\) столбцов.
Вы можете выполнять над ней два типа действий:
- покрасить весь столбец в синий;
- покрасить всю строку в красный.
Обратите внимание, что вы не можете выбирать, в какой цвет красить строку или столбец.
За одну секунду можно выполнить как одно действие, так и несколько одновременно. Если сделать одно действие, то это будет бесплатно. Если же сделать \(k > 1\) действий одновременно, то на это придется потратить \(k^2\) монет. Когда несколько действий выполняются одновременно, для каждой клетки, которая затрагивается действиями обоих типов, цвет можно выбрать независимо.
Требуется обработать \(q\) запросов. Перед каждым запросом все ячейки становятся бесцветными. Изначально ограничений на итоговый цвет клеток нет. В \(i\)-м запросе добавляется ограничение вида:
- \(x_i~y_i~c_i\) — клетка в строке \(x_i\) в столбце \(y_i\) должна быть покрашена в цвет \(c_i\).
Таким образом, после \(i\) запросов существует \(i\) ограничений на необходимые цвета клеток матрицы. После каждого запроса выведите минимальную стоимость покраски в соответствии с ограничениями.