Problems
Embedded circles
Embedded circles
You are given a table \{\textbf{a_ij}\} of \textbf{R} rows and \textbf{C} columns, consisting of digits from '\textbf{0}' to '\textbf{9}'. Respond \textbf{Q} queries of a kind:
\textbf{ik jk rk},\textbf{ 1} ≤ \textbf{ k} ≤ \textbf{Q}
Find the sum of all such elements \textbf{a_ij}, that \textbf{(i-i_k)^2 + (j-j_k)^2} ≤ \textbf{r^2_k}.
Summation area for each query is something like circle with center in cell (\textbf{i_k}, \textbf{j_k}) and radius \textbf{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 \textbf{k} and \textbf{l} (\textbf{k} < \textbf{l}) have common cells, then for any \textbf{t}: \textbf{k} < \textbf{t} ≤ \textbf{l}, circle \textbf{t} is fully contained in the circle of query \textbf{k}. Circles of dierent queries can coinside.
\InputFile
First line contains two numbers \textbf{R} and \textbf{C} that are table size. Then \textbf{R} lines with \textbf{C} numbers in each (no spaces between numbers) follow. The next line has number \textbf{Q} --- amount of querries. Each of the next \textbf{Q} lines describes a querry with three integers: \textbf{i_k}, \textbf{j_k} (central cell row and coloumn numbers) and \textbf{r_k} (circle radius).
\OutputFile
Because of large number of queries, output the sum of answers for all queries.
\textbf{Limits}
\textbf{1} ≤ \textbf{R}, \textbf{C} ≤ \textbf{2000}
'\textbf{0}' ≤ \textbf{a_ij} ≤ '\textbf{9}'
\textbf{1} ≤ \textbf{Q} ≤ \textbf{10^6}
\textbf{1 + r_k} ≤ \textbf{i_k} ≤ \textbf{R-r_k}
\textbf{1 + r_k} ≤ \textbf{j_k} ≤ \textbf{C-r_k}
\includegraphics{https://static.e-olymp.com/content/b8/b80835090ad73b7e88c2acaa042ea527893733fe.jpg}
\textbf{0} ≤ \textbf{r_k} ≤
Input example #1
6 6 123456 234567 345678 456789 567890 678901 10 1 1 0 3 3 2 3 2 1 2 2 0 4 2 0 1 3 0 2 3 0 4 3 0 5 5 1 5 5 0
Output example #1
141
Example description: 141 = 1 + 65 + 20 + 3 + 5 + 3 + 4 + 6 + 25 + 9