Aquapark

An aquapark is shaped like a square with side length $n$ and is divided into $n^2$ unit cells of side $1$. Each cell is either a pool or a walkway. A pool cell has a positive number of children playing in it; a walkway has none.

There are $r$ lifeguards on duty. Under the safety rules a lifeguard may move only parallel to the walls, so the distance between two cells $(x_1, y_1)$ and $(x_2, y_2)$ is always the Manhattan distance $|x_1 - x_2| + |y_1 - y_2|$. Lifeguard $i$ is responsible for every pool that lies at distance at most $l_i$ from their position.

A lifeguard's workload is the total number of children in all the pools they guard. Determine the workload of every lifeguard.

The first line contains two integers $n$ and $r$ ($1 \le n \le 1000$, $1 \le r \le n^2$): the side length of the aquapark and the number of lifeguards.

Each of the next $n$ lines describes one row of the map. The $i$-th line contains $n$ non-negative integers $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($0 \le a_{i,j} \le 10^6$). If $a_{i,j} = 0$, cell $(i, j)$ is a walkway; otherwise it is a pool holding $a_{i,j}$ children.

Each of the next $r$ lines describes one lifeguard with three integers $x_i$, $y_i$, $l_i$ ($1 \le x_i, y_i \le n$, $1 \le l_i \le n$): the row and column of the lifeguard's position, and the maximum distance to the pools they guard.

Print exactly $r$ lines. The $i$-th line must contain a single integer $p_i$: the number of children guarded by lifeguard $i$.