A railway line (not a circular one) has $n$ stations, numbered $1, \ldots, n$ in order. There are $n$ types of trains running on this line, numbered $1, \ldots, n$. Each type of train operates in both directions.

Each station on this railway line has a passenger traffic volume, which is a positive integer $\le n$. The passenger traffic volume of station $i$ ($1 \le i \le n$) is $a_i$.

A train of type $j$ ($1 \le j \le n$) stops only at stations where the passenger traffic volume is $\ge j$. A passenger can depart from station $x$, board any train that stops at $x$, and travel along the direction of the train to the next station $y$ where that train stops. If the train is traveling to the left, i.e., $y < x$, the passenger must pay $l_x$ ddtt coins; otherwise, if the train is traveling to the right, i.e., $y > x$, the passenger must pay $r_x$ ddtt coins.

It is guaranteed that for $1 \le i \le n-1$, $l_i \le l_{i+1}$ and $r_i \ge r_{i+1}$.

There are $q$ passengers, numbered $1, \ldots, q$. Passenger $k$ ($1 \le k \le q$) has a starting station $s_k$ and a destination station $t_k$ ($1 \le s_k, t_k \le n$). Assume these passengers can only move using this railway line.

For each passenger, calculate the minimum number of ddtt coins required to reach their destination. It is guaranteed that the starting station and destination station for each passenger are different. Moving back and forth is allowed. There are multiple test cases.

Input

The first line contains a positive integer $T$ ($1 \le T \le 3 \cdot 10^4$), representing the number of test cases.

For each test case, the first line contains two integers $n, q$ ($1 \le n, q \le 3 \cdot 10^5$), representing the number of stations and the number of passengers.

The second line contains $n$ integers $a_1, \ldots, a_n$, representing the passenger traffic volume of the stations.

The next $n$ lines each contain two positive integers $l_i, r_i$ ($1 \le l_i, r_i \le 10^9, l_i \le l_{i+1}, r_i \ge r_{i+1}$).

The next $q$ lines each contain two positive integers $s_k, t_k$ ($1 \le s_k, t_k \le n$).

Output

For each passenger, output the minimum number of ddtt coins required to reach the destination.

Examples

Input 1

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

Output 1

33
9
6
8
17
0

Constraints

It is guaranteed that $\sum n, \sum q \le 3 \cdot 10^5$, $1 \le l_i, r_i \le 10^9$, and $1 \le s_k, t_k \le n$.

It is guaranteed that $l_i \le l_{i+1}$ and $r_i \ge r_{i+1}$.

Subtask 1 (3 pts): $\sum n \le 400$.

Subtask 2 (14 pts): $\sum n, \sum q \le 5000$.

Subtask 3 (21 pts): $\sum n \le 5000$.

Subtask 4 (20 pts): $l_i = r_i = 1$ ($1 \le i \le n$).

Subtask 5 (42 pts): No additional restrictions.