Embedded circles#4597
You are given a table a_{ij} of rows and columns, consisting of digits from '0' to '9'. Respond to queries of the following kind:
i_k j_k r_k, 1 \leq k \leq Q
Find the sum of all such elements a_{ij} that (i - i_k)^2 + (j - j_k)^2 \leq r_k^2.
The summation area for each query is similar to a circle with its center at cell (i_k, j_k) and radius r_k. The area is defined exactly by the above formula, but we will refer to it as a circle for convenience.
For any two queries, the following conditions are satisfied: either their circles have no common table cells, or one of the circles is fully contained within the other.
Furthermore, queries are sorted by insertion. That is, if the circles of queries and (k < l) have common cells, then for any with k < t \leq l, the circle is fully contained within the circle of query . Circles of different queries may coincide.
The first line contains two numbers and representing the table size. Then lines follow, each containing digits (no spaces between numbers).
The next line contains the number —the number of queries. Each of the next lines describes a query with three integers: i_k, j_k (central cell row and column numbers), and r_k (circle radius).
Because of the large number of queries, output the sum of answers for all queries.
Limits
1 \leq R, C \leq 2000
0 \leq a_{ij} \leq 9
1 \leq Q \leq 10^6
1 + r_k \leq i_k \leq R - r_k
1 + r_k \leq j_k \leq C - r_k
Example 1