Description

YSGH has a permutation $p$ of $1 \sim n$ and an integer sequence $w$ of length $n$.

Define:

$$F(l, r) = \begin{cases} \max(F(l, m - 1), F(m + 1, r)) + w_m & , l \le r \\ 0 & , l > r \end{cases}$$

where $m$ is the index of the maximum value of $p$ in the interval $[l, r]$.

There are $q$ queries asking for the value of $F(l, r)$.

Input Format

The first line contains two positive integers $n, q$, with the same meaning as in the statement.

The second line contains $n$ positive integers. The $i$-th integer is $p_i$, with the same meaning as in the statement.

The third line contains $n$ integers. The $i$-th integer is $w_i$, with the same meaning as in the statement.

The next $q$ lines each contain two positive integers $l, r$ ($1 \le l \le r \le n$), representing a query for $F(l, r)$.

Output Format

Output $q$ lines. Each line contains one integer, which is the answer.

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

7
2

Hint

This problem uses bundled testdata.

• Subtask 1 (10 points): $n, q \le 5 \times {10}^3$.
• Subtask 2 (10 points): It is guaranteed that $p$ is random.
• Subtask 3 (20 points): $n, q \le 5 \times {10}^4$.
• Subtask 4 (20 points): $n, q \le {10}^5$.
• Subtask 5 (20 points): $w_i \ge 0$.
• Subtask 6 (20 points): No special constraints.

For $100\%$ of the data, $1 \le n, q \le 5 \times {10}^5$, $|w_i| \le 10^9$, $1 \le p_i \le n$. It is guaranteed that $p$ is a permutation of $1 \sim n$.

Translated by ChatGPT 5