题目描述

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

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

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

数据保证对于 $1\leq i\leq n-1$ ，有 $ l_i\leq l_{i+1}, r_i\geq 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\leq T\leq 3\cdot 10^4)$ ，表示数据组数。

接下来对于每组数据，第一行包含两个整数 $n,q(1\leq n,q\leq 3\cdot 10^5)$ ，表示车站数量和旅客数量。

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

接下来 $n$ 行，每行两个正整数 $l_i,r_i(1\leq l_i,r_i\leq 10^9,l_i\leq l_{i+1},r_i\geq r_{i+1})$ 。

接下来 $q$ 行，每行两个正整数 $s_k,t_k(1\leq s_k,t_k\leq 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\leq 3\cdot 10^5, 1\leq l_i,r_i\leq 10^9,1\leq s_k,t_k\leq n$ 。

保证 $l_i\leq l_{i+1},r_i\geq r_{i+1}$ 。

subtask1(3pts)：保证 $\sum n\leq 400$ 。

subtask2(14pts)：保证 $\sum n,\sum q\leq 5000$ 。

subtask3(21pts)：保证 $\sum n\leq 5000$ 。

subtask4(20pts)：保证 $l_i=r_i=1(1\leq i\leq n)$ 。

subtask5(42pts)：无特殊限制。

时间限制：5s

空间限制：1GB