题目描述

某条铁路线（非环线）有 $n$ 站，依次编号为 $1,\ldots,n$。这条线路上跑着 $n$ 类列车，编号为 $1,\ldots,n$。每种列车都是双向运行的。

这条铁路线上的每个车站都有个旅客流量，旅客流量是一个 $\le n$ 的正整数。车站 $i\ (1\le i\le n)$ 的旅客流量为 $a_i$。

第 $j$ 类列车（$1\le j\le n$）在且只在旅客流量 $\ge j$ 的车站停车。一名旅客可以从 $x$ 站出发，乘上任意一辆在 $x$ 停车的列车，沿着列车的方向行驶到该列车的下一个停车的车站 $y$。如果列车是向左行驶的，即 $y<x$，那么旅客需要花费 $l_x$ ddtt 币；否则列车是向右行驶的，即 $y>x$，此时旅客需要花费 $r_x$ ddtt 币。

数据保证对于 $1\le i\le n-1$，有 $l_i\le l_{i+1}$、$r_i\ge r_{i+1}$。

现有 $q$ 名旅客，依次编号为 $1,\ldots,q$，旅客 $k\ (1\le k\le q)$ 的起点是车站 $s_k$，终点是 $t_k\ (1\le s_k,t_k\le n)$。假设这些旅客只能靠这条铁路线移动。

对于每名旅客，求这名旅客到达终点至少需要花费多少 ddtt 币。保证同一名旅客的起点与终点不同。允许走回头路。多组测试。

输入格式

第一行一个正整数 $T\ (1\le T\le 3\cdot 10^4)$，表示数据组数。

接下来对于每组数据：

第一行包含两个整数 $n,q\ (1\le n,q\le 3\cdot 10^5)$，表示车站数量和旅客数量。

第二行包含 $n$ 个整数 $a_1,\ldots,a_n$，表示车站的旅客流量。

接下来 $n$ 行，每行两个正整数 $l_i,r_i\ (1\le l_i,r_i\le 10^9)$。

接下来 $q$ 行，每行两个正整数 $s_k,t_k\ (1\le s_k,t_k\le n)$。

输出格式

对每名旅客，输出他到达终点至少需要花费的 ddtt 币数量。

样例

样例输入 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

样例输出 1

33
9
6
8
17
0

数据范围

保证 $\sum n,\sum q\le 3\cdot 10^5$，$1\le l_i,r_i\le 10^9$，$1\le s_k,t_k\le n$。

保证 $l_i\le l_{i+1}$、$r_i\ge r_{i+1}$。