暂无测试数据。

小 C 现在探索一个 $n*n$ 的迷宫，每个位置有一个柱子，现在给每行一个整数，第 $i$ 行的整数为 $R_i$ ，给每列一个整数，第 $i$ 列的整数为 $C_i$，那么第 $i$ 行第 $j$ 列的位置 $(i,j)$ 处柱子的高度就是 $R_i*C_j$ 。

迷宫里的路径是从起点处的柱子开始，每次只能相邻向下或向右的柱子移动，到达终点，沿路经过的所有点形成的路径。一条合法路径是整条路径（包括起点、终点）上经过的柱子的高度都是 $0$ 的路径，现在小 C 有一种魔法，可以选定一个素数 $M$ ，然后让 $(i, j)$ 处的柱子高度变为 $R_i*C_j \mod M$ 。

小 C 现在有 $q$ 个询问，每次给出起点坐标 $(r_a,c_a)$ 终点坐标 $(r_b,c_b)$，对于每次询问他想知道是否能用魔法创造出一条合法的路径，如果有请问 $M$ 最大是多少。

需要注意的是，每次询问独立，即对于每次询问，不受之前询问所使用的魔法干扰，本次使用魔法前每个位置柱子的高度均为最初的 $R_i*C_j$ 。

输入格式

第一行两个整数分别表示 $n$ 和 $q$

第二行有 $n$ 个整数，第 $i$ 个整数表示 $R_i$

第三行有 $n$ 个整数，第 $i$ 个整数表示 $C_i$

接下来 $q$ 行每行 $4$ 个整数，分别表示一次询问的 $r_a,c_a,r_b,c_b$

输出格式

对于每次询问，如果不存在符合题意的素数 $M$ 则输出 $-1$，否则输出 $M$ 的最大值

数据范围

对于 $20\%$ 的数据, $1 \leq n,q \leq 100$

对于 $50\%$ 的数据, $1 \leq n,q \leq 10000$

对于 $100\%$ 的数据, $1 \leq n,q \leq 100000,1 \leq R_i,C_i \leq 1000$

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

2
3
-1