建筑物距离
题号：NC16433
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

    广阔的ACM大陆上，建筑物星罗棋布般地分布，而每个建筑物都是不同ACM团队的驻地。

    ACM大陆为n*m的矩阵，分成n*m个格子。对于两个相邻的格子，若它们都是建筑物的一部分，则这两个格子属于同一个建筑物。

    作为ACM大陆的管理者，你需要为ACM初学者提供两个建筑物之间的曼哈顿距离（Manhattan Distance）。

    其 中：

    两个格子 , 之间的曼哈顿距离：

    两个建筑物 , 之间的曼哈顿距离：    

输入描述:

第1行输入两个整数n,m（1<=n<=1000,1<=m<=1000）。

第2行~第2+n-1行输入n*m的矩阵，0代表这个格子不是建筑物的一部分，1代表这个格子是建筑物的一部分。数据保证建筑物数目小于等于50。

第3行输入q，代表询问对数(1<=q<=500)。

接下来的q行输入四个整数。请求出所在的建筑物与所在的建筑物之间的曼哈顿距离。数据保证,格子的数值均为1。数据有可能出现两个建筑物相同的情况。

输出描述:

输出q行，依次为所在的建筑物与所在的建筑物之间的曼哈顿距离。
示例1

输入

复制 
3 4
1 0 1 1
1 0 0 1
0 1 0 0
4
1 1 2 4
1 1 3 2
3 2 1 4
2 4 1 3

输出

复制 
2
2
3
0

说明


1 1 2 4：(1,1)->(1,2)->(1,3)
1 1 3 2：(2,1)->(3,1)->(3,2)
3 2 1 4：(3,2)->(3,3)->(3,4)->(2,4)或(3,2)->(3,3)->(2,3)->(2,4)
2 4 1 3：两个格子在同一个建筑物中

备注:

输入数据较多，请注意读入读出。