Problem Description

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

Little D has a positive integer sequence $a_1, a_2, \dots, a_n$ and an integer sequence $b_1, b_2, \dots, b_n$.

Little D has $q$ queries. In each query, $x, y$ are given, and a new sequence $c_1, c_2, \dots, c_n$ is constructed, where $c_i=\begin{cases}1 & a_i=x \\-1 & a_i=y \\ 0 & \text{else}\end{cases}$.

It is guaranteed that among the $c_i$ there is at least one $1$ and at least one $-1$. He wants you to find an interval $[l,r]$ such that $\sum\limits_{i=l}^r c_i=0$, and $\sum\limits_{i=l}^r b_i \times [c_i \neq 0]$ is maximized, and the $c_i$ in the interval cannot all be $0$. You need to output this maximum value.

Note: When the condition $[P]$ is true, $[P]=1$, otherwise $[P]=0$.

Input Format

The first line contains two integers $n, q$.
The second line contains $n$ integers, where the $i$-th integer denotes $a_i$.
The third line contains $n$ integers, where the $i$-th integer denotes $b_i$.
The next $q$ lines each contain two integers $x, y$, representing one query.

Output Format

For each query, output one line with one integer, representing the maximum value of $\sum\limits_{i=l}^r b_i \times [c_i \neq 0]$.

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

2
1
5

见附加样例文件中的 ex_sequence2.in

见附加样例文件中的 ex_sequence2.out

Hint

Constraints

This problem has $20$ test points.

• For test points $1,2,3,4$, it is guaranteed that $n, q \le 5000$.
• For test points $5,6$, it is guaranteed that the number of distinct values in $a$ does not exceed $500$.
• For test points $7,8$, it is guaranteed that $n \le 150000$, $q \le 500000$, and $b_i>0$.
• For test point $9$, it is guaranteed that $n \le 150000$ and $q \le 500000$.
• For test points $10,11$, it is guaranteed that $n \le 200000$ and $q \le 500000$.
• For test points $12,13,14$, it is guaranteed that $b_i=1$.
• For test points $15,16$, it is guaranteed that $b_i>0$.

For all test points, $1 \le n \le 300000$, $1 \le q \le 1000000$, $1 \le a_i \le n$, $-10^9<b_i \leq 10^9$, $1 \leq x, y \leq n$, $x \neq y$. It is guaranteed that for each query, the $c_i$ always contain at least one $1$ and at least one $-1$.

Translated by ChatGPT 5