洋流

题号：NC235817
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一片 $n\times m$ 海域的洋流地图，其中每一个位置都有一个洋流。每次你可以向北、东北、东、东南、南、西南、西或者西北移动，并且不能离开这片海域。如果你当前坐标是 $(x,y)$ ，按照上述方向移动后，你分别能达到坐标 $(x-1,y)$ 、 $(x-1,y+1)$ 、 $(x,y+1)$ 、 $(x+1,y+1)$ 、 $(x+1,y)$ 、 $(x+1,y-1)$ 、 $(x,y-1)$ 和 $(x-1,y-1)$ 。当你顺着洋流走时不消耗体力，否则你需要消耗1点体力。现给出 $T$ 组询问，每组询问需要你回答从坐标 $(x_1,y_1)$ 到 $(x_2,y_2)$ 最少消耗多少体力。

输入描述:

第一行输入两个整数  ，表示这片海域的大小。
接下来  行，每行  个整数，以数字0-7来表示每一个位置的洋流方向。0表示洋流向北、1表示洋流向东北、2表示洋流向东...依此类推。
接下来一行输入一个整数  ，表示询问的个数。
接下来  行，每行输入四个整数  ，以空格分离，代表一个询问。

输出描述:

输出行，对于每一个询问，输出一行一个整数，表示从到最少消耗多少体力。

示例1

输入

复制

输出

复制

0
2
1