汉堡

题目背景

在夜黑风高的晚上，一旦闻到汉堡的香味，就会忍不住地想吃汉堡...

题目描述

$P$市 可以看作一张$n*m$的方格图，每个方格只有$0$和$1$两种情况，其中$0$表示空地，$1$表示汉堡店。

$piggy$为了减肥，制定了一个时长为$T$天的减肥计划：第$i$天，$piggy$会在第$0$分钟开始从$(a_i,b_i)$出发，跑步到$(c_i,d_i)$。

当$piggy$在$(x,y)$处，那么$piggy$可以花费一分钟时间跑到与$(x,y)$四联通的方格即：$(x+1,y)$，$(x,y+1)$，$(x-1,y)$，$(x,y-1)$

古话说的好，先帝创业未半而中道崩殂

每天的第$0$分钟，没有任何一个方格有汉堡香味。

汉堡店在第$0$分钟做好了汉堡，并在汉堡店产生了汉堡香味，后续每一分钟，含有汉堡香气的方格$(x,y)$会飘向所有与之四联通的方格

注意：汉堡香味在某个方格一旦存在，便不会散去

$piggy$一旦闻到汉堡香味，就会忍不住地想终止当天计划去买汉堡，即$piggy$在任意时刻不能处于一个含有汉堡香气的方格

幸运的是，猪猪丸可以帮助$piggy$抵抗诱惑，吃一颗猪猪丸可以帮助$piggy$在汉堡香气里待一分钟

猪猪丸吃多了，对身体不好，因此，你需要告诉$piggy$每天最少需要吃多少猪猪丸才能完成当天计划

输入描述

第一行，两个整数$n$，$m$

接下来$n$行，每行$m$个整数，$0$表示是空地，$1$表示汉堡店

第$n+2$行，一个整数$T$

接下来$T$行，每行四个整数，$a_i,b_i,c_i,d_i$

输出描述

共$T$行，每行一个整数，表示当天最少需要吃多少猪猪丸

样例输入

3 3
000
101
111
2
1 2 1 1
1 1 1 2

样例输出

1
0

数据范围

$30pts:$$n,m\leq 10$

$60pts:$$n,m\leq 100$

$100pts:$$n,m\leq 1000$

对于所有数据$T \leq 5$，并且保证$(a_i,b_i),(c_i,d_i)$不在汉堡店处

对于$100pts$的数据范围，其中有$10pts$的数据保证地图没有汉堡店