几乎所有的蝉在幼年时期都会在地下度过，之后才会破土而出，进入为期几周到几个月的短暂成年阶段。

七种周期蝉之所以得名，是因为在任何一个地点，该种群的所有成员在发育上都是同步的，它们每隔七年就会同时作为成虫出现。

大多数周期蝉的生命周期在两年到十七年之间，尽管有些可能更长。

有一片森林，可以大致划分为一个 $N \times M$ 的矩阵。左上角区域为 $(1, 1)$，右下角区域为 $(N, M)$。

矩阵的每个区域内都生活着一个周期蝉种群。区域 $(i, j)$ 的种群在 $a_{i,j}$ 年第一次出现，并且每 $b_{i,j}$ 年重新出现一次。也就是说，它们是 $b_{i,j}$ 周期的蝉。

给定一个选定的矩形区域，昆虫学家想知道是否存在一个时间点，使得该区域内所有的蝉同时出现。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例以两个整数 $N$ 和 $M$ 开头。

接下来的 $N$ 行，每行包含 $M$ 个整数 $a_{i,j}$，表示区域 $(i, j)$ 的蝉第一次出现的年份。

再接下来的 $N$ 行，每行包含 $M$ 个整数 $b_{i,j}$，表示该区域蝉的周期。

随后是一行，包含一个整数 $Q$，表示查询的数量。接下来的 $Q$ 行，每行包含 4 个整数 $x_1, y_1, x_2, y_2$，表示所选矩形区域的左上角和右下角坐标。

输出格式

对于每个测试用例，首先输出一行 “Case #x:”，其中 $x$ 是测试用例的编号（从 1 开始）。

接下来的 $Q$ 行，每行输出一个整数，表示所选区域内所有蝉第一次同时出现的年份，如果不可能，则输出 $-1$。

数据范围

• $1 \le T \le 10$
• $1 \le N, M \le 200$
• $0 \le a_{i,j} < b_{i,j} \le 40$
• $1 \le x_1 \le x_2 \le N$
• $1 \le y_1 \le y_2 \le M$
• $1 \le Q \le 500000$

样例

样例输入 1

2
3 4
3 1 1 2
1 1 2 1
1 0 5 5
5 4 2 3
2 2 3 2
4 2 6 6
5
2 2 2 2
1 1 3 4
1 4 2 4
1 1 1 2
2 2 3 4
1 2
0 1
2 2
1
1 1 1 2

样例输出 1

Case #1:
1
-1
5
13
-1
Case #2:
-1