### 问题描述 小蓝考上了世界上最好的魔法师学校，然而入学第一件事就是智力测试，老师给出了一个 $n \times m$ 大小的棋盘，同时对每行每列设置了权重 $\lbrace R_{1},R_{2},\cdots ,R_{n}\rbrace$ 和 $\lbrace C_{1},C_{2},\cdots ,C_{m} \rbrace$，因此，对于第 $r$ 行第 $c$ 列的格子 $(r, c)$，其权重为一个二元组 $(R_{r},C_{c})$ 。 小蓝可以在格子之间进行移动，若某时刻小蓝在格子 $( r, c)$，那么他可以一步走到任意的格子 $ (r^{\prime }, c)$ 或 $(r,{c}^{\prime })$，其中 ${r}^{\prime },{c}^{\prime }$ 满足: 1. $R_{{r}^{\prime }} > R_{r},C_{{c}^{\prime }} > C_{c}$。 2. `$\nexists {r}^{\prime \prime } \cdot {R}_{{r}^{\prime }} > {R}_{{r}^{\prime \prime }} > {R}_{r};\nexists {c}^{\prime \prime } \cdot {C}_{{c}^{\prime }} > {C}_{{c}^{\prime \prime }} > {C}_{c}$` 。 之后，老师提出了 $T$ 个问题，第 $i$ 个问题为：假设小蓝从格子 `$\left( {{s}_{r}^{i},{s}_{c}^{i}}\right)$` 出发，移动到格子 `$\left( {{t}_{r}^{i},{t}_{c}^{i}}\right)$` 有多少种不同的走法，答案对 $\text{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$ 行，每行包含一个整数，依次表示每个问题的答案。 ### 样例输入 ```text 4 4 2 4 2 3 1 2 1 2 1 4 4 1 1 2 2 2 4 ``` ### 样例输出 ```text 4 0 ``` ### 样例说明 询问 $1$： $\left( {4,4}\right) \rightarrow \left( {2,4}\right) \rightarrow \left( {3,4}\right) \rightarrow \left( {1,4}\right) \rightarrow \left( {1,1}\right)$ $\left( {4,4}\right) \rightarrow \left( {2,4}\right) \rightarrow \left( {3,4}\right) \rightarrow \left( {3,1}\right) \rightarrow \left( {1,1}\right)$ $\left( {4,4}\right) \rightarrow \left( {2,4}\right) \rightarrow \left( {2,1}\right) \rightarrow \left( {3,1}\right) \rightarrow \left( {1,1}\right)$ $\left( {4,4}\right) \rightarrow \left( {4,1}\right) \rightarrow \left( {2,1}\right) \rightarrow \left( {3,1}\right) \rightarrow \left( {1,1}\right)$ 。 询问 $2$： 不存在方案可以从 $\left( {2,2}\right)$ 走到 $\left( {2,4}\right)$。 ### 评测用例规模与约定 对于 ${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$`。