智力测试
题号：NC309411
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小蓝考上了世界上最好的魔法师学校，然而入学第一件事就是智力测试。老师给出了一个 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，且不存在 r'' 使得 R_{r'} > R_{r''} > R_r。即 R_{r'} 必须是所有行权重中，比 R_r 大的数值里最小的那个（紧邻的下一级权重）。
2. **列移动规则**：C_{c'} > C_c，且不存在 c'' 使得 C_{c'} > C_{c''} > C_c。即 C_{c'} 必须是所有列权重中，比 C_c 大的数值里最小的那个。

简而言之，小蓝每次只能让行权重或列权重“升级”到紧邻的下一个等级。

之后，老师提出了 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 行，每行包含一个整数，依次表示每个问题的答案。
示例1

输入

复制 
4 4 2
4 2 3 1
2 1 2 1
4 4 1 1
2 2 2 4

输出

复制 
4
0

说明

**询问 1：**
- (4, 4) \to (2, 4) \to (3, 4) \to (1, 4) \to (1, 1)
- (4, 4) \to (2, 4) \to (3, 4) \to (3, 1) \to (1, 1)
- (4, 4) \to (2, 4) \to (2,1) \to (3,1) \to (1, 1)
- (4, 4) \to (4,1) \to (2,1) \to (3, 1) \to (1, 1)
**询问 2：**
不存在方案可以从 (2,2) 走到 (2,4)。

备注:

- 对于 20% 的评测用例，1 \le n, m, T \le 10^3。
- 对于所有评测用例，1 \le n, m, T \le 10^5，1 \le R_i, C_i \le 10^8，1 \le s_r^i, t_r^i \le n，1 \le s_c^i, t_c^i \le m。