Little D learned how to create problems when he was three years old.

Little D has a sequence of positive integers $a_1, a_2, \cdots, a_n$ and a sequence of integers $b_1, b_2, \cdots, b_n$.

Little D has $q$ queries. Each query provides $x$ and $y$. Construct a new sequence $c_1, c_2, \cdots, c_n$, where $c_i = \begin{cases}1 & a_i=x\\-1 & a_i = y\\ 0 & \mathrm{else}\end{cases}$. It is guaranteed that $c_i$ contains at least one $1$ and at least one $-1$. You need to find an interval $[l, r]$ such that $\sum\limits_{i=l}^r c_i=0$, and the value $\sum\limits^r_{i=l}b_i \times [c_i \ne 0]$ is maximized. The interval must contain at least one non-zero $c_i$. You need to output this maximum value.

Input

The first line contains two integers $n$ and $q$.

The second line contains $n$ integers $a_i$.

The third line contains $n$ integers $b_i$.

The next $q$ lines each contain two integers $x$ and $y$, representing a query.

Output

Output $q$ lines, each containing an integer representing the maximum value of $\sum\limits_{i=l}^r b_i \times [c_i\ne 0]$.

Examples

Input 1

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

Output 1

2
1
5

Input 2

See the provided files.

Subtasks

There are 20 test cases in total.

For test cases 1, 2, 3, 4, $n, q \leq 5000$.

For test cases 5, 6, the number of distinct values of $a_i$ does not exceed 500.

For test cases 7, 8, $n \leq 150\,000$, $q \leq 500\,000$, $b_i > 0$.

For test case 9, $n \leq 150\,000$, $q \leq 500\,000$.

For test cases 10, 11, $n \leq 200\,000$, $q \leq 500\,000$.

For test cases 12, 13, 14, $b_i = 1$.

For test cases 15, 16, $b_i > 0$.

For all test cases, $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$. It is guaranteed that for each query, $c_i$ contains at least one $1$ and at least one $-1$.