Alice 是一位出色的玩偶制作师，她拥有许多玩偶。她有 $n$ 个玩偶，编号从 $1$ 到 $n$。每个玩偶的颜色要么是红色，要么是黑色。每个玩偶还有一个独特的价值。

每天，Alice 会从编号范围 $[l, r]$ 中选择两个玩偶进行表演。如果她能找到两个编号为 $i$ 和 $j$ 的玩偶，满足：1) 玩偶 $i$ 和玩偶 $j$ 颜色相同且价值满足 $v_i < v_j$，并且 2) 不存在一个编号 $k \in [l, r]$ 的玩偶，其颜色与 $i, j$ 不同且价值满足 $v_i < v_k < v_j$，那么 Alice 在这次表演中可以获得 $v_j - v_i$ 的分数。否则，她也可以选择什么都不做，获得零分。

现在 Alice 需要最大化每天表演的分数。你能帮她计算出每天的最大分数吗？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^4$) —— 玩偶的数量。

下一行包含 $n$ 个整数，其中第 $i$ 个数是 $c_i$ ($c_i \in \{0, 1\}$) —— 玩偶 $i$ 的颜色（1 代表红色，0 代表黑色）。

再下一行包含 $n$ 个整数，其中第 $i$ 个数是 $v_i$ ($1 \le v_i \le 10^9$，且所有 $v_i$ 互不相同) —— 玩偶 $i$ 的价值。

接下来一行包含一个整数 $m$ ($1 \le m \le 10^6$) —— 天数。

接下来的 $m$ 行，每行包含两个数字 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$) —— 第 $i$ 天候选玩偶的编号范围 $[l_i, r_i]$。

输出格式

输出包含 $m$ 行，每行一个整数。

第 $i$ 行的整数是 Alice 在第 $i$ 天能获得的最大分数。

特别地，如果 Alice 找不到满足条件的玩偶 $i$ 和 $j$，你应该输出 0。

样例

输入 1

5
1 0 0 0 1
4 5 3 1 2
5
1 3
2 4
2 5
1 5
1 1

输出 1

0
4
2
0
0

说明

请使用快速输入输出。