It's Jack's first day of freshman year at the University of Fireloo! He looks at his timetable but is disappointed to find that he has to take data management again. Having grown tired of drawing charts, he decides to challenge himself to draw as efficiently as he can!

Today, Jack is trying to draw a histogram! A histogram consists of $N$ bars of positive height, $h_1,h_2,\dots ,h_N$ with widths $w_1,w_2,\dots ,w_N$ respectively. He considers a drawing of a histogram to be complete if the four sides of each rectangular bar have been traced over at least once and there are no extraneous marks on the sheet. He realizes that since all bars are adjacent, he can make his drawing complete without removing his pencil from the drawing once he chooses where to start drawing. And in order to assess his efficiency, he wishes to find the optimal way to draw that minimizes the total distance travelled by his pencil tip during the entire process.

Having experimented with this challenge for a few hours now, he has analyzed $Q$ scenarios, where in the $i$-th scenario, he draws all bars from $l_i$ to $r_i$ inclusive. Help him determine the minimal distance his pencil needs to travel in each scenario!

Constraints

In all subtasks,
$1\le N,Q\le 100000$
$1\le w_i,h_i\le 1000000$
$1\le l_i\le r_i\le N$

Subtask 1 [5%]

$r_i-l_i\le 1$

Subtask 2 [5%]

$1\le N\le 5$
$1\le Q\le 100$

Subtask 3 [10%]

All $h_i$ are equal. That is, $h_1=h_2=\cdots =h_N$.

Subtask 4 [10%]

$1\le N,Q\le 1000$
$w_i=1$

Subtask 5 [10%]

$Q=1$

Subtask 6 [60%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, $N$ $Q$.
The second line contains $N$ space-separated integers, $h_1,h_2,\dots ,h_N$.
The third line contains $N$ space-separated integers, $w_1,w_2,\dots ,w_N$.
The next $Q$ lines contain two space-separated integers, $l_i$ $r_i$.

Output Specification

Output $Q$ integers on separate lines. The $i$-th integer should be the answer to the $i$-th query.

Sample Input 1

5 6
3 5 8 2 4
1 2 1 1 2
1 3
2 4
1 5
4 5
2 3
3 3

Sample Output 1

34
32
50
16
27
18

Explanation for Sample Output 1

In the diagram of Sample Input 1, the numbers at the bottom indicate the width of each bar while the numbers inside each bar indicate the height of the bar. Suppose we apply a coordinate system to this diagram with the bottom-left corner of the first bar being at $(0,0)$.
For the first query, one optimal way to draw would be:

• Start drawing at $(1,3)$
• Move $1$ unit left to $(0,3)$
• Move $3$ units down to $(0,0)$
• Move $4$ units right to $(4,0)$
• Move $8$ units up to $(4,8)$
• Move $1$ unit left to $(3,8)$
• Move $8$ units down to $(3,0)$
• Move $2$ units left to $(1,0)$
• Move $5$ units up to $(1,5)$
• Move $2$ units right to $(3,5)$

The total distance moved is $34$ units. The boundaries of the first three bars have been drawn over at least once and it is impossible to do so using a shorter distance.

Sample Input 2

10 7
2 4 3 2 3 1 4 3 2 4
2 6 5 3 7 6 1 5 2 3
3 6
6 7
1 3
1 9
2 8
8 9
4 7

Sample Output 2

58
23
41
119
103
22
52

Explanation for Sample Output 2

Sample Input 3

10 5
1 2 3 4 5 8 6 3 2 1
1 1 1 1 1 1 1 1 1 1
2 6
1 8
3 5
7 10
4 9

Sample Output 3

44
64
24
28
54

Explanation for Sample Output 3