说明

时间限制：2 Sec 内存限制：256 MB 输入文件：route.in 输出文件：route.out

小明的家可以表示为一个 $H$ 行 $W$ 列的网格，从上往下第 $i$ 行、从左往右第 $j$ 列的格子记为 $(i,j)$。格子 $(i,j)$ 的移动难度为 $A_{i,j}$。

他可以向上下左右相邻的格子移动。

当发生等级为 $K$ 的灾害时，小明移动的耗时规则如下：

- 若他依次经过格子 $(i_1,j_1),(i_2,j_2),\dots,(i_G,j_G)$（包含起点和终点），

- 总耗时为：$ (K^2+A_{i_1,j_1})+(K^2+A_{i_2,j_2})+\dots+(K^2+A_{i_G,j_G}) $

- 他不能重复经过同一个格子。

他家的紧急出口在格子 $(gx,gy)$。

请回答 $Q$ 个询问：

- 当小明在格子 $(x_i,y_i)$ 时发生等级 $k_i$ 的灾害，他到达紧急出口逃生至少需要多少秒？

输入格式

第一行两个整数 $H,W$。

第二行两个整数 $gx,gy$。

接下来 $H$ 行，每行 $W$ 个整数 $A_{i,1},A_{i,2},\dots,A_{i,W}$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行三个整数 $x_i,y_i,k_i$。

输出格式

共 $Q$ 行，第 $i$ 行输出第 $i$ 个询问的答案。

样例

样例 1

4 5
1 1
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4
5
3 1 1
1 1 7
4 5 3
3 2 5
3 5 2

20
52
102
114
54

样例说明：

第一个询问中，从 $(3,1)$ 沿路径 $(3,1)\to(2,1)\to(1,1)$ 移动，耗时为：$(1^2+5)+(1^2+9)+(1^2+3)=20$。

样例 2

7 7
7 3
1 1 1 1 1 1 1
99 99 99 99 99 99 1
99 1 1 1 1 1 1
99 1 99 99 99 99 99
99 1 1 1 1 1 99
99 99 99 99 99 1 99
99 99 1 1 1 1 99
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10

50
125
248
349
430
529
646
781
934
1105

样例 3

7 7
7 6
1 1 1 1 1 1 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 1 1
2
1 1 4
1 1 5

238
352

数据范围

对于 40% 的数据，$H,W \le 10$，$Q \le 100$。

对于 100% 的数据，$1 \le H,W \le 250$，$1 \le Q \le 500000$，$1 \le A_{i,j} \le 99$，$1 \le x_i \le H,\ 1 \le y_i \le W$，$1 \le k_i \le 1000000$，$1 \le gx \le H,\ 1 \le gy \le W$。