Embedded circles
Дана таблица {a_ij} из R строк и C столбцов, состоящая из цифр от '0' до '9'. Требуется ответить на Q запросов вида:
ik jk rk, 1 ≤ k ≤ Q
Найти сумму всех элементов таблицы a_ij таких, что (i-i_k)^2 + (j-j_k)^2 ≤ r^2_k.
Область суммирования для каждого запроса представляет собой нечто, похожее на круг с центром в ячейке (i_k, j_k) и радиусом r_k. Область определяется в точности по формуле выше, но для удобства будем называть ее кругом.
Для любых двух запросов выполняется следующее: либо их круги не имеют общих ячеек таблицы, либо один из кругов полностью содержится в другом.
Более того, запросы идут в порядке вложенности. Это означает, что если круги запросов k и l (k < l) имеют общие ячейки, то из этого следует, что для любого t: k < t ≤ l, круг t полностью содержится в круге запроса k. Круги различных запросов могут совпадать.
Входные данные
В первой строке два числа R и C — размеры таблицы. Далее R строк по C цифр в каждой (между цифрами нет пробелов). В следующей строке число Q — количество запросов. Далее в Q строках описаны запросы по три целых числа в каждой строке i_k, j_k, r_k — номера строки и столбца центральной ячейки и радиус круга. Ячейки нумеруются с 1.
Поскольку запросов много, выведите одно число — сумму всех ответов на запросы.
Ограничения
1 ≤ R, C ≤ 2000
'0' ≤ a_ij ≤ '9'
1 ≤ Q ≤ 10^6
1 + r_k ≤ i_k ≤ R-r_k
1 + r_k ≤ j_k ≤ C-r_k
0 ≤ r_k ≤