개구리와 쿼리

$N \times N$ 크기의 $2$차원 배열로 이루어진 연못에 $Q$마리의 개구리가 모여 있다. 각 개구리는 초기 위치 $\left(S\\_{x},S\\_{y}\right)$에서 배열의 오른쪽 끝 $\left(X,N+1\right)$에 있는 육지에 도착해야 한다.

개구리는 현재 칸에서 $Y$좌표가 $1$만큼 증가하는 방향, 즉 오른쪽으로 이동할 수 있다. 이때 현재 칸에 적힌 값만큼 시간이 소모된다. 또한 각 개구리는 최대 한 번 점프할 수 있으며, 점프를 한다면 개구리마다 정해진 하한 값 $L$ 이상 점프해야 한다.

점프는 $X$좌표가 감소하는 방향, 즉 위쪽으로 이동하는 것이며 시간이 소모되지 않는다.

개구리의 초기 위치와 점프 하한 값이 다음과 같은 쿼리 형태로 주어질 때

• $S\\_{x}$ $S\\_{y}$ $L$ : 개구리의 초기 위치가 $\left(S\\_{x},S\\_{y}\right)$이고 최대 한 번 $L$ 이상의 양의 정수 값 $T$만큼 점프할 수 있을 때, 육지에 도달하는 데 걸리는 최단 시간을 출력하라. $\left(S\\_{x} > L\right)$

각 쿼리에 대해서 옳은 답을 차례대로 출력하자.

입력의 첫 줄에 $2$차원 배열의 크기를 나타내는 $N$과 개구리의 수 $Q$가 공백으로 구분되어 정수로 주어진다. $(3 \le N \le 500;$ $1 \le Q \le 200 \\, 000)$

입력의 두 번째 줄부터 $N$개의 줄에 배열 $A$에 적힌 값이 공백으로 구분되어 정수로 주어진다. $i+1$번째 줄의 $j$번째 수는 배열의 $i$번째 행 $j$번째 열의 적힌 값 A\\[i\\]\\[j\\]을 나타낸다. (0 \le A\\[i\\]\\[j\\] \le 10\\,000)

입력의 $N+2$ 줄부터 $Q$개의 줄에 쿼리가 정수로 주어진다. $(0 \le L < S\\_{x} \le N;$ $1 \le S\\_{y} \le N)$

$Q$개의 줄에 차례대로 쿼리의 정답을 정수로 출력하라.