题目描述

给出一个 $1,\dots,n+1$ 的排列 $v_{1,\dots,n+1}$，与两组权值 $a_{1,\dots,n}$、$b_{1,\dots,n}$。满足 $v_{n+1}=n+1$。

构造一张 $n+1$ 个点的 有向图：

• 对于 $i=1,\dots,n$，从 $i$ 向 $i+1$ 连一条权值为 $a_i$ 的边；
• 对于 $i=1,\dots,n$，找到最小的 $i < j \le n+1$ 满足 $v_j>v_i$，从 $i$ 向 $j$ 连一条权值为 $b_i$ 的边。

一条路径的权值为路径上边权的 最大值。特别地，若一条路径不包含任何边，则其权值为 $0$。

有 $q$ 次询问，每次询问给出 $x,y$（$x \le y$），求 $x$ 到 $y$ 的权值最小的路径的权值。

输入格式

输入的第一行包含三个数 $n,q,S$。其中 $S$ 表示测试点所属的子任务编号。第二行包含 $n$ 个数，表示 $v_{1,\dots,n}$。第三行包含 $n$ 个数，表示 $a_{1 ,\dots,n}$。第四行包含 $n$ 个数，表示 $b_{1,\dots,n}$。 接下来 $q$ 行，其中第 $i$ 行包含两个数 $x,y$，表示第 $i$ 次询问。

输出格式

输出应包含 $q$ 行，第 $i$ 行包含一个数，表示你对第 $i$ 个询问求出的答案。

样例数据

样例 1 输入

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

样例 1 输出

2
3
3
5
3
0

样例 2

见下发文件 ex_jump2.in 和 ex_jump2.out，该测试用例满足子任务 1 的约束 条件。

样例 3

见下发文件 ex_jump3.in 和 ex_jump3.out，该测试用例满足子任务 1 的约束 条件。

样例 4 输入

8 10 2
8 7 6 5 4 3 2 1 
5 2 3 5 9 4 3 8 
7 3 4 4 1 2 8 3 
1 3
6 8
7 9
9 9
1 9
1 8
4 4
2 9
2 6
1 3

样例 4 输出

5
4
3
0
5
9
0
3
9
5

样例 5

见下发文件 ex_jump5.in 和 ex_jump5.out，该测试用例满足子任务 2 的约束 条件。

样例 6

见下发文件 ex_jump6.in 和 ex_jump6.out，该测试用例满足子任务 3 的约束 条件。

样例 7

见下发文件 ex_jump7.in 和 ex_jump7.out，该测试用例满足子任务 3 的约束 条件。

样例 8

见下发文件 ex_jump8.in 和 ex_jump8.out。

样例 9

见下发文件 ex_jump9.in 和 ex_jump9.out。

数据规模与约定

全部数据均保证 $1 \le n,q \le 5 \times 10^5$，$1 \le a_i,b_i \le 10^9$，$1 \le x \le y \le n+1$。

本题采用子任务捆绑测试，各个子任务详细信息如下：

下发样例