题目描述

小蓝考上了世界上最好的魔法师学校，然而入学第一件事就是智力测试，老师给出了一个 $n \times m$ 大小的棋盘，同时对每行每列设置了权重 $\{R_1, R_2, \cdots, R_n\}$ 和 $\{C_1, C_2, \cdots, C_m\}$，因此，对于第 $r$ 行第 $c$ 列的格子 $(r, c)$，其权重为一个二元组 $(R_r, C_c)$。

小蓝可以在格子之间进行移动，若某时刻小蓝在格子 $(r, c)$，那么他可以一步走到任意的格子 $(r', c)$ 或 $(r, c')$，其中 $r', c'$ 满足：

（1）$R_{r'} > R_r, C_{c'} > C_c$，

（2）$\nexists r''. R_{r'} > R_{r''} > R_r; \nexists c''. C_{c'} > C_{c''} > C_r$。

之后，老师提出了 $T$ 个问题，第 $i$ 个问题为：假设小蓝从格子 $(s_r^i, s_c^i)$ 出发，移动到格子 $(t_r^i, t_c^i)$ 有多少种不同的走法，答案对 $1000000007$ 取模。

输入格式

输入的第一行包含三个正整数 $n, m, T$，相邻整数之间使用一个空格分隔。

第二行包含 $n$ 个正整数 $R_1, R_2, \cdots, R_n$，相邻整数之间使用一个空格分隔。

第三行包含 $m$ 个正整数 $C_1, C_2, \cdots, C_m$，相邻整数之间使用一个空格分隔。

接下来 $T$ 行，第 $i$ 行包含四个正整数 $s_r^i, s_c^i, t_r^i, t_c^i$，相邻整数之间使用一个空格分隔。

输出格式

输出 $T$ 行，每行包含一个整数，依次表示每个问题的答案。

4 4 2
4 2 3 1
2 1 2 1
4 4 1 1 
2 2 2 4

4
0

提示

【样例说明】

询问 1：

• $(4, 4) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (1, 4) \rightarrow (1, 1)$;
• $(4, 4) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 1) \rightarrow (1, 1)$;
• $(4, 4) \rightarrow (2, 4) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (1, 1)$;
• $(4, 4) \rightarrow (4, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (1, 1)$。

询问 2：

• 不存在方案可以从 $(2, 2)$ 走到 $(2, 4)$。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，$1 \leq n, m, T \leq 10^3$；

对于所有评测用例，$1 \leq n, m, T \leq 10^5$，$1 \leq R_i, C_i \leq 10^8$，$1 \leq s_r^i, t_r^i \leq n$，$1 \leq s_c^i, t_c^i \leq m$。