Embedded circles

You are given a table {a_ij} of R rows and C columns, consisting of digits from '0' to '9'. Respond Q queries of a kind:

ik jk rk, 1 ≤ k ≤ Q

Find the sum of all such elements a_ij, that (i-i_k)^2 + (j-j_k)^2 ≤ r^2_k.

Summation area for each query is something like circle with center in cell (i_k, j_k) and radius r_k. Area is de ned exactly by the formula above, but we will call it a circle for convenience.

For any two queries the following conditions are satis ed: either their circles have no common table cells, or one of the circles is fully contained in another.

Furthermore, queries are sorted by insertion. That means, that if circles of queries k and l (k < l) have common cells, then for any t: k < t ≤ l, circle t is fully contained in the circle of query k. Circles of dierent queries can coinside.

Input

First line contains two numbers R and C that are table size. Then R lines with C numbers in each (no spaces between numbers) follow. The next line has number Q — amount of querries. Each of the next Q lines describes a querry with three integers: i_k, j_k (central cell row and coloumn numbers) and r_k (circle radius).

Output

Because of large number of queries, output the sum of answers for all queries.

Limits

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 ≤

Examples