정거장

A시의 중심 도로를 따라 $n$개의 버스 정류장과 $n$개의 버스 노선이 있다. 정류장은 왼쪽에서 오른쪽으로 1번부터 $n$번까지 번호가 붙어 있고, 정류장 $i$의 중요도는 $a_i$이다. 버스 노선도 1번부터 $n$번까지 번호가 붙어 있다. $k$번 노선의 버스는 중요도가 $k$ 이상인 모든 정류장에 선다. 각 노선은 양방향으로 운행한다.

정류장 $x$에 있는 관광객은 $x$에 서는 버스 아무 것이나 탈 수 있고, 방향을 하나 골라 그 방향으로 버스가 다음에 방문하는 정류장 $y$까지 갈 수 있다. 이런 정류장이 있을 때만 가능하다. 이동 비용은 $y < x$이면 $l_x$위안, $y > x$이면 $r_x$위안이다. 관광객은 목적지에 도달하기 위해 버스를 여러 번 탈 수 있다.

관광객은 $q$명이다. $j$번째 관광객은 정류장 $s_j$에서 $t_j$까지 이동하려 한다. 각 관광객에 대해 경로의 최소 비용을 구하라.

모든 $i$ ($1 \le i \le n-1$)에 대해 $l_i \le l_{i+1}$이고 $r_i \ge r_{i+1}$이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 3 \cdot 10^4$). 각 테스트 케이스는 정류장의 수 $n$과 관광객의 수 $q$를 나타내는 두 정수로 시작한다 ($1 \le n, q \le 3 \cdot 10^5$).

다음 줄에는 $a_1, \ldots, a_n$이 주어진다 ($1 \le a_i \le n$). 이어서 $n$개의 줄이 주어지며, $i$번째 줄에는 $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}$). 그 다음 $q$개의 줄에는 각각 $s_j$와 $t_j$가 주어진다 ($1 \le s_j, t_j \le n$).

모든 테스트 케이스에 걸친 $n$의 합과 $q$의 합은 각각 $3 \cdot 10^5$을 넘지 않는다.

각 관광객에 대해 최소 비용을 한 줄에 하나씩 출력한다.