小 D 三岁就学会了出题。

小 D 有一个正整数序列 $a_1, a_2, \cdots, a_n$ 和一个整数序列 $b_1,b_2,\cdots,b_n$。

小 D 有 $q$ 次查询，每次给出 $x,y$，构造一个新的序列 $c_1,c_2,\cdots,c_n$，其中 $c_i = \begin{cases}1 & a_i=x\\-1 & a_i = y\\ 0 & \mathrm{else}\end{cases}$。保证 $c_i$ 中至少存在一个 $1$ 与 $-1$。他想让你帮他找到一个区间 $[l, r]$，满足 $\sum\limits_{i=l}^r c_i=0$，并使得 $\sum\limits^r_{i=l}b_i \times [c_i \ne 0]$ 最大，并且区间里的 $c_i$ 不能都为 $0$。你需要输出这个最大值。

输入格式

第一行两个整数 $n, q$。

第二行 $n$ 个整数 $a_i$。

第三行 $n$ 个整数 $b_i$。

接下来 $q$ 行，每行两个整数 $x,y$，表示一次询问。

输出格式

$q$ 行，每行一个整数表示最大的 $\sum\limits_{i=l}^r b_i \times [c_i\ne 0]$。

样例数据

样例 1 输入

5 3
1 2 3 1 2
-2 3 2 -1 2
1 2
1 3
2 3

样例 1 输出

2
1
5

样例 2

见下发文件。

子任务

一共 $20$ 个测试点。

对于测试点 $1,2,3,4$，$n,q \leq 5000$。

对于测试点 $5,6$，$a_i$ 的取值不超过 $500$ 种。

对于测试点 $7, 8$，$n \leq 150\,000$，$q \leq 500\,000$，$b_i > 0$。

对于测试点 $9$，$n \leq 150\,000$，$1 \leq 500\,000$。

对于测试点 $10,11$，$n \leq 200\,000$，$q \leq 500\,000$。

对于测试点 $12,13,14$，$b_i=1$。

对于测试点 $15,16$，$b_i > 0$。

对于所有测试点，$1 \leq n \leq 300\,000$，$1 \leq q \leq 1\,000\,000$，$1 \leq a_i \leq n$，$-10^9 \leq b_i \leq 10^9$，$1 \leq x,y \leq n$，$x \ne y$，保证对于每次查询，$c_i$ 中均至少含有一个 $1$ 与一个 $-1$。