Statement is not available in English language
D. Последнее испытание
ограничение по времени на тест
15 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Этот день настал! Сегодня, после стольких лет тренировок, Эш наконец-то попал на всемирный турнир тренеров покемонов, где у него будет шанс побороться за звание лучшего тренера покемонов в мире. Успешно справившись с несколькими этапами соревнования, Эш попал в финал, в котором тренированных покемонов проверяют на умение быстро строить оптимальные маршруты.

Один раунд соревнования выглядит следующим образом: покемона помещают в левую верхнюю клетку прямоугольного поля. В каждой клетке поля записано целое число  — количество очков, которое покемон получает, когда наступает на эту клетку (в клетке может быть записано отрицательное число, это означает, что в случае, если покемон наступает на эту клетку, его количество очков уменьшается). Задача покемона  — добежать до правой нижней клетки поля, получив наибольшее количество очков; при этом правилами турнира разрешено перемещаться за один шаг только на одну клетку вправо или на одну клетку вниз.

Перед началом соревнования Эш решил лишний раз удостовериться, что его лучший покемон  — Пикачу умеет строить оптимальные маршруты; для этого он играет с ним в следующую игру: Эш показывает Пикачу поле и задает ему $$$q$$$ вопросов вида «какой наибольший счет можно было бы получить на этом поле, если бы в клетке с координатами $$$(i, j)$$$ было записано число $$$x$$$ вместо того, что там записано сейчас?».

Эш попросил вас написать программу, которая найдет правильные ответы на все вопросы, чтобы он мог убедиться, что Пикачу готов к финальному соревнованию.

Входные данные

В первой строке через пробел записаны 3 числа: $$$n$$$, $$$m$$$ и $$$q$$$ ($$$1 \le n, m \le 1\,000$$$, $$$1 \le q \le 5 \cdot 10^5$$$)  — высота поля, ширина поля и количество вопросов соответственно. Далее в $$$n$$$ строках записано по $$$m$$$ целых чисел  — значения, которые записаны в клетках поля, не превосходят $$$10^6$$$ по абсолютному значению. Далее в $$$q$$$ строках записано по 3 целых числа $$$i$$$, $$$j$$$ и $$$x$$$ ($$$1 \le i \le n, 1 \le j \le m, -10^6 \le x \le 10^6$$$)  — номер строки, столбца клетки и новое значение клетки поля соответственно. Строки нумеруются сверху вниз, начиная с 1, столбцы нумеруются слева направо, начиная с 1.

Выходные данные

Для каждого вопроса выведите одно число  — наибольший счет, который можно получить на данном поле с измененным значением одной клетки.

Система оценки

Гарантируется, что решения, работающие корректно при $$$n$$$, $$$m$$$, $$$q \le 4$$$, будут получать не менее 10 баллов.

Гарантируется, что решения, работающие корректно при $$$n$$$, $$$m$$$, $$$q \le 10$$$, будут получать не менее 24 баллов.

Гарантируется, что решения, работающие корректно при $$$n$$$, $$$m$$$, $$$q \le 100$$$, будут получать не менее 40 баллов.

Гарантируется, что решения, работающие корректно при $$$n$$$, $$$m \le 300$$$, $$$q \le 6\,000$$$, будут получать не менее 60 баллов.

Гарантируется, что решения, работающие корректно при $$$n$$$, $$$m \le 700$$$, $$$q \le 10^5$$$, будут получать не менее 80 баллов.

Примеры
Входные данные
3 3 5
1 2 3
4 5 6
7 8 9
3 1 0
3 3 -100
2 2 10
1 2 2
3 2 1
Выходные данные
27
-80
32
29
25
Входные данные
1 4 3
5 3 2 4
1 3 5
1 2 0
1 1 -20
Выходные данные
17
11
-11