UOJ Logo Universal Online Judge

UOJ

#118. 【UR #8】赴京赶考

统计

高中,高中,短暂的三年。NOI是高中结业考试,而高考在每年暑假举行。

高二暑假,这是你最后一次参加高考的机会。你已经为了高考停课很久了,OI的知识很久没管了。你并没有能力用一年时间补起别人三年的OI课程。这是你的最后一战,如果你失败了,可能就不能工地搬砖只能去清华了。

这天你背上行囊赴京赶考。此时全国交通主要靠瞬间传送装置。全国交通网络可以抽象为一张 $n$ 行 $m$ 列的网格图。行依次编号为 $1, \dots, n$,列依次编号为 $1, \dots, m$。

有 $n + m$ 个为 $0$ 或 $1$ 的整数 $a_1, \dots, a_n, b_1, \dots, b_m$。对于 $1 \leq i \leq n$,$1 \leq j \leq m$,如果 $a_i = b_j$ 那么网格图上第 $i$ 行第 $j$ 列上标着 $0$ 否则标着 $1$。

你的家在第 $x_s$ 行第 $y_s$ 列,高考考场在第 $x_e$ 行第 $y_e$ 列。现在你想从家出发到高考考场去。每次你可以:

  1. 向上移动一行。(如果你在第一行那么移动后会到最后一行去)
  2. 向下移动一行。(如果你在最后一行那么移动后会到第一行去)
  3. 向左移动一列。(如果你在第一列那么移动后会到最后一列去)
  4. 向右移动一列。(如果你在最后一列那么移动后会到第一列去)

对于每次移动,如果移动前的格子上标的数跟移动后的格子上标的数不同,那么就要耗费 $1$ 分钟时间等待瞬移装置调整配置,否则不耗时间。

现在你想知道你从家出发到高考考场最少需要花多长时间。

输入格式

第一行两个正整数 $n, m$,表示网格图为 $n$ 行 $m$ 列。

第二行 $n$ 个整数,分别表示 $a_1, \dots, a_n$。保证 $a_1, \dots, a_n \in \{0, 1\}$。

第三行 $m$ 个整数,分别表示 $b_1, \dots, b_m$。保证 $b_1, \dots, b_m \in \{0, 1\}$。

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

接下来 $q$ 行,每行四个整数 $x_s, y_s, x_e, y_e$。表示询问如果你的家在第 $x_s$ 行第 $y_s$ 列,高考考场在第 $x_e$ 行第 $y_e$ 列时的最少花费时间。

输出格式

共 $q$ 行,每行一个整数表示最少花费多少分钟。

样例一

input

1 2
1
0 1
2
1 2 1 2
1 1 1 2

output

0
1

样例二

input

10 10
1 1 0 1 1 1 0 1 0 1
0 0 1 0 1 1 0 0 1 0
4
7 6 4 8
8 2 1 4
8 5 7 4
3 1 9 5

output

2
4
2
5

限制与约定

测试点编号 $n, m$的规模 $q$的规模
1$n, m \leq 100$$q \leq 10$
2
3
4$n \leq 10^5, m = 1$$q \leq 10^5$
5
6$n, m \leq 10^5$$q \leq 10^5$
7
8
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载