Зима в Лилипутии
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лилипутия представляет собой прямоугольную таблицу $$$n \times m$$$. В этом году в Лилипутии выдалась суровая зима: на город падают массивные снежинки.

Синоптики собрали срочное совещание и выяснили, в какие точки будут падать снежинки. Каждая снежинка будет покрывать некоторые клетки таблицы: центральную клетку с лучами длины $$$k$$$ клеток в 8 сторон: в обе стороны по горизонтали, в обе стороны по вертикали и в четыре стороны по диагоналям.

У центральной клетки снежинки толщина $$$k$$$. По мере удаления от центральной клетки на каждом из 8 лучей толщина уменьшается на один с каждой следующей клеткой: $$$k, k-1, \ldots, 1$$$. Например, если $$$k=3$$$:

0000000

0101010

0022200

0123210

0022200

0101010

0000000

Помогите лилипутам узнать для каждой клетки города, какой суммарной толщиной снега она будет покрыта.

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

В первой строке вводятся два целых числа $$$n, m$$$ ($$$1 \leq n \cdot m \leq 10^6$$$) — размеры города.

Во второй строке вводится единственное целое число $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — количество снежинок, которые упадут на Лилипутию.

В последующих $$$q$$$ строках вводятся описания снежинок: на $$$i$$$-й строке три целых числа $$$a_i, b_i, k_i$$$ ($$$1 \leq a_i \leq n, 1 \leq b_i \leq m, 1 \leq k_i \leq 10^6$$$) — координаты центральных клеток снежинок, а также длины лучей.

Обратите внимание, что луч снежинки может выходить за пределы города.

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

Выведите $$$n$$$ строк по $$$m$$$ чисел: в $$$i$$$-й строке на $$$j$$$-й позиции суммарная толщина частей снежинок, которые упали на эту клетку.

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

Решения, верно работающие при $$$n \cdot m \cdot q \le 1e8$$$, будут получать не менее 24 баллов. Решения, верно работающие при $$$\max{(n, m)} \cdot q \le 1e8$$$, будут получать не менее 48 баллов.

Примеры

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

    7 714 4 3

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

    0 0 0 0 0 0 0
    0 1 0 1 0 1 0
    0 0 2 2 2 0 0
    0 1 2 3 2 1 0
    0 0 2 2 2 0 0
    0 1 0 1 0 1 0
    0 0 0 0 0 0 0

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

    7 724 4 32 3 10

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

    0 9 9 9 0 0 0
    8 10 10 10 8 8 6
    0 9 11 11 2 0 0
    8 1 10 3 10 1 0
    0 0 9 2 2 7 0
    0 1 6 1 0 1 6
    0 0 5 0 0 0 0