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 ≤