Recursive Maximum Query Recurrence

You are given a permutation p of the integers from 1 to n and an integer sequence w of length n.

The function F(l,r) is defined recursively as:

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

Here, m is the index within the interval \([l, r]\) at which p attains its maximum value.

You will be given q queries. In each query, you are given two integers l and r and you must compute F(l, r) for the corresponding subarray.

Note: The indices in the input are 1-indexed.

inputFormat

The first line contains two integers n and q -- the number of elements and the number of queries.

The second line contains n integers representing the permutation p of 1 through n.

The third line contains n integers representing the sequence w.

Each of the next q lines contains two integers l and r, representing a query to compute F(l, r).

outputFormat

For each query, output a single integer: the value of F(l,r).

sample

3 3
2 3 1
1 2 3
1 1
1 3
2 3

1
5
5

</p>