Aquapark

한 워터파크는 한 변의 길이가 $n$인 정사각형 모양이며, 한 변이 $1$인 단위 칸 $n^2$개로 나뉘어 있습니다. 각 칸은 수영장이거나 통로입니다. 수영장 칸에는 양의 정수만큼의 아이가 놀고 있고, 통로 칸에는 아이가 없습니다.

워터파크에는 $r$명의 안전요원이 배치되어 있습니다. 안전 규정상 안전요원은 벽과 나란한 방향으로만 이동할 수 있으므로, 두 칸 $(x_1, y_1)$과 $(x_2, y_2)$ 사이를 이동하는 거리는 항상 맨해튼 거리 $|x_1 - x_2| + |y_1 - y_2|$입니다. $i$번째 안전요원은 자신의 위치로부터 거리가 $l_i$ 이하인 모든 수영장을 담당합니다.

한 안전요원의 업무량은 자신이 담당하는 모든 수영장에 있는 아이 수의 합입니다. 모든 안전요원의 업무량을 구하세요.

첫째 줄에 두 정수 $n$과 $r$이 공백으로 구분되어 주어집니다 ($1 \le n \le 1000$, $1 \le r \le n^2$). 각각 워터파크의 한 변의 길이와 안전요원의 수를 뜻합니다.

이어지는 $n$개의 줄에는 워터파크의 지도가 주어집니다. $i$번째 줄에는 $i$번째 행을 나타내는 $n$개의 음이 아닌 정수 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($0 \le a_{i,j} \le 10^6$)이 공백으로 구분되어 주어집니다. $a_{i,j} = 0$이면 칸 $(i, j)$는 통로이고, 양수이면 아이 $a_{i,j}$명이 있는 수영장입니다.

이어지는 $r$개의 줄에는 각 안전요원의 정보가 세 정수 $x_i$, $y_i$, $l_i$ ($1 \le x_i, y_i \le n$, $1 \le l_i \le n$)로 주어집니다. 각각 $i$번째 안전요원이 있는 칸의 행과 열, 그리고 담당하는 수영장까지의 최대 거리를 뜻합니다.

정확히 $r$개의 줄을 출력합니다. $i$번째 줄에는 $i$번째 안전요원이 담당하는 아이의 수를 나타내는 정수 $p_i$ 하나를 출력합니다.