有 $n$ 个清扫机器人在一条直线上，从左到右第 $i$ 个机器人的代价为 $c_i$。保证所有的 $c_i$ 互不相同。第 $i$ 个机器人和第 $(i+1)$ 个机器人之间的距离为 $d_i$。

当你想要清扫第 $l$ 个机器人到第 $r$ 个机器人之间的区间时，你首先会贪心地选择该区间内代价最小的机器人。然后，该机器人会寻找一条覆盖该区间内每个机器人至少一次的路径，且路径长度尽可能小。注意，机器人不需要返回其初始位置。定义区间 $[l, r]$ 的代价为所选机器人的代价乘以所选路径的长度。

你需要回答 $q$ 个询问，每个询问如下：对于给定的区间 $[l, r]$，在所有满足 $l \le l' \le r' \le r$ 的区间 $[l', r']$ 中，最大代价是多少？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)。

第二行包含 $n$ 个整数，其中第 $i$ 个为 $c_i$ ($1 \le c_i \le n$)。

第三行包含 $n - 1$ 个整数，其中第 $i$ 个为 $d_i$ ($1 \le d_i \le 10^5$)。

第四行包含一个整数 $q$ ($1 \le q \le 10^6$)。

接下来的 $q$ 行描述询问，其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)。

输出格式

输出量较大，因此你只需要输出 $1$ 个整数——这 $q$ 个询问答案的异或和（XOR sum），其中第 $i$ 个整数应为区间 $[l_i, r_i]$ 的答案。

样例

输入样例 1

5
4 1 5 2 3
2 8 4 2
4
3 5
1 2
2 4
1 3

输出样例 1

18