问题描述

有一个 $H$ 行 $W$ 列的网格房间。我们将第 $i (1 ≦ i ≦ H)$ 行第 $j (1 ≦ j ≦ W)$ 列的格子称为格子 $(i,j)$。相邻格子之间有门，开关这些门的代价是确定的。开关门的代价都是大于等于 $1$ 的整数。对于所有 $i (2 ≦ i ≦ H), j (2 ≦ j ≦ W)$，以下条件都成立：

• 格子 $(i-1,j-1)$ 和格子 $(i-1,j)$ 之间的门开关代价是 $A$。
• 格子 $(i,j-1)$ 和格子 $(i,j)$ 之间的门开关代价是 $B$。
• 格子 $(i-1,j-1)$ 和格子 $(i,j-1)$ 之间的门开关代价是 $C$。
• 格子 $(i-1,j)$ 和格子 $(i,j)$ 之间的门开关代价是 $D$。
• 满足 $A+D = B+C$ 且 $A+C ≦ B+D$。

我们将从格子 $(si,sj)$ 移动到格子 $(ti,tj)$，每次只能上下左右移动相邻格子，移动过程中会经过一些门，移动的总门开关代价称为 $dist(si,sj,ti,tj)$ 的最小值。注意，移动时经过的门开关代价只包括相邻格子之间的门。另外，对于任意 $i,j$，可以假设 $dist(i,j,i,j) = 0$。

你知道 $H$ 和 $W$ 的值，但不知道门开关代价的信息。首先要回答以下问题：

• $dist(si,sj,ti,tj)$ 的值是多少？

问法如下形式，一共进行 $H \times W$ 次：

$si$ $sj$ $ti$ $tj$

接下来会再次回答 $Q$ 个类似形式的问题：

• $dist(Si,Sj,Ti,Tj)$ 的值是多少？

问法如下形式：

$Si$ $Sj$ $Ti$ $Tj$

然后程序需要输出 $dist(Si,Sj,Ti,Tj)$ 的值。

问题回答完毕后，程序必须立即结束。若没有结束，则评判结果未定义。

同时，如果回答有错误的情况下也是未定义的（不一定是 WA）。

注意，在输出完毕后，需要执行 flush 操作。若没有执行 flush，可能会超时。

每种语言的输入输出方法可以参考过去在 AtCoder 上出现的问题（链接：ABC 019 D: 高橋くんと木の直径）。

输入输出示例

说明

程序的输出

程序的输入

给出了网格的行数和列数以及问题的数量。

2 2 2

询问了 $dist(1,1,2,2)$ 的值。

1 1 2 2

给出了问题的答案。

6

再次询问 $dist(1,1,2,2)$ 的值。

1 1 2 2

给出了问题的答案。

6

询问 $dist(2,1,2,1)$ 的值。

2 1 2 1

给出了问题的答案。

0

询问 $dist(2,2,1,1)$ 的值。

2 2 1 1

给出了问题的答案。

6

被询问 $dist(1,1,2,2)$ 的值。

1 1 2 2

输出了问题的答案。

6

被询问 $dist(1,2,1,2)$ 的值。

1 2 1 2

输出了问题的答案。

0