题目背景

游戏 Minecraft 中的恼鬼是一种很厉害的生物，有着很高的伤害，超小的碰撞箱，并且可以无视任何方块穿墙。

题目描述

有一块 $n\times m$ 的区域，第 $i$ 行第 $j$ 列的最下方有 $h _ {i, j}$ 个方块，而在这些方块的上方则都是空气。每个方块都是一个 $1\times 1\times 1$ 的立方体。在这个区域外则全都是空气。

有 $q$ 只恼鬼。恼鬼希望一直在方块中躲藏移动来偷袭，因此它们不能进入空气。恼鬼会一直处于某个方块中间，可以用该方块的行、列和高度来描述一个恼鬼的位置。恼鬼可以移动，前后左右移动一格不需要耗费体力，而上下移动则需要 $1$ 点体力。

第 $i$ 只恼鬼刚开始时在 $ax _ i$ 行 $ay _ i$ 列最高的方块中，它想移动到 $bx _ i$ 行 $by _ i$ 列最高的方块中。请求出它的体力消耗最小值。

输入格式

第一行两个正整数 $n, m$。

接下来 $n$ 行每行 $m$ 个正整数表示每个位置的方块数。

接下来一行一个正整数 $q$。

接下来 $q$ 行，第 $i$ 行四个正整数表示 $ax _ i, ay _ i, bx _ i, by _ i$。

输出格式

$q$ 行，每行一个整数表示答案。

样例

样例输入 1

3 3
9 4 7 
8 1 7 
1 2 1 
4
1 3 2 3
3 1 3 2
1 2 3 1
2 1 1 1

样例输出 1

0
1
3
1

样例输入/输出 2

见下发文件 vex2.in/ans。该样例满足测试点 $6 \sim 8$ 的限制。

样例输入/输出 3

见下发文件 vex3.in/ans。该样例满足测试点 $9 \sim 11$ 的限制。

数据范围与提示

本题共 $20$ 个测试点，每个测试点 $5$ 分。

对于所有数据，$1 \le n \times m \le 10 ^ 6$，$1 \le q \le 5 \times 10 ^ 5$，$1 \le h _ {i, j} \le 10 ^ 9$，$1 \le ax _ i, bx _ i \le n$，$1 \le ay _ i, by _ i \le m$。