题目背景

YSGH is our red sun.

题目描述

YSGH 有一个 $1 \sim n$ 的排列 $p$ 和一个长度为 $n$ 的整数序列 $w$。

定义：

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

其中 $m$ 为 $p$ 的区间 $[l, r]$ 的最大值的下标。

$q$ 次询问 $F(l, r)$ 的值。

输入格式

第一行两个正整数 $n, q$，意义同题目描述。

第二行共 $n$ 个正整数，第 $i$ 个表示 $p_i$，意义同题目描述。

第三行共 $n$ 个整数，第 $i$ 个表示 $w_i$，意义同题目描述。

接下来共 $q$ 行，每行两个正整数 $l, r$（$1 \le l \le r \le n$），表示询问 $F(l,r)$。

输出格式

输出共 $q$ 行，每行一个整数，表示答案。

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

7
2

提示

本题采用捆绑测试。

• Subtask 1（10 points）：$n, q \le 5 \times {10}^3$。
• Subtask 2（10 points）：保证 $p$ 是随机的。
• 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）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n, q \le 5 \times {10}^5$，$|w_i| \le 10^9$，$1 \le p_i \le n$，保证 $p$ 是一个 $1 \sim n$ 的排列。