Non-Cat-Rinks

Input

The first line contains two integers $n$ and $q$ (1 \le n,\,q \le 3 \cdot 10^5)—the number of vertices and the number of clients wishing to purchase vertices.

The second line contains $n$ integers h_1, h_2, \ldots, h_n (2 \le h_i \le 3 \cdot 10^5)—the values of the vertices.

The third line contains $n$ integers a_1, a_2, \ldots, a_n (0 \le a_i \le 10^6)—the number of coins required to decrease the value of a vertex by one.

The next $q$ lines contain two integers $l$ and $r$ (1 \le l,\ l+2 \le r \le n)—the boundaries of the segment that interests the client.

Output

For each query, you must output one number—the minimum number of coins needed to be able to form the tree.

Examples

Note

For the first query, the optimal arrangement is a star graph with the central vertex $1$ and leaves $2,3,4$, as shown below:

In this tree, the longest path passing through any vertex has a length of $2$:

• For the center $(1)$: between leaves $2$ and $4$ —$2$ edges.

• For any leaf: between $3$ and $2$ —$2$ edges.

Thus, we need all h_i=2, so the cost is calculated as follows:

1. Vertex $1$: 2 \rightarrow 2, so the cost is $0$.

2. Vertex $2$: 3 \rightarrow 2, so the cost is $4$.

3. Vertex $3$: 4 \rightarrow 2, so the cost is $10$.

4. Vertex $4$: 5 \rightarrow 2, so the cost is $9$.

As a result, the total cost is $23$.

For the second query, the optimal arrangement is a linear graph.

The length of the path is $2$, so each vertex must end up with h_i=2.

1. Vertex $3$: 2 \rightarrow 2, so the cost is $10$.

2. Vertex $4$: 3 \rightarrow 2, so the cost is $9$.

3. Vertex $5$: 4 \rightarrow 2, so the cost is $6$.

As a result, the total cost is $25$.

Scoring

1. Subtask $1$ ($10$ points) : (q=1, l=1, r=n)

2. Subtask $2$ ($10$ points) : (h_1 = h_2 = h_3 = ... = h_n)

3. Subtask $3$ ($20$ points) : (n \le 10^5,\ h_i = i+1)

4. Subtask $4$ ($20$ points) : (r-l=3)

5. Subtask $5$ ($30$ points) : (l=1)

6. Subtask $6$ ($30$ points) : (1 \le n, q \le 500)

7. Subtask $7$ ($40$ points) : (1 \le n, q \le 2000)

8. Subtask $8$ ($40$ points) : (1 \le n, q \le 2 \cdot 10^4)

9. Subtask $9$ ($50$ points) : (1 \le n, q \le 10^5)

10. Subtask $10$ ($150$ points) : Without additional constraints