题目描述
某条铁路线（非环线）有 n 站，依次编号为 1,…,n。这条线路上跑着 n 类列车，编号为 1,…,n。每种列车都是双向运行的。
这条铁路线上的每个车站都有个旅客流量，旅客流量是一个 ≤n 的正整数。车站 i(1≤i≤n) 的旅客流量为 ai 。
第 j 类列车 (1≤j≤k) 在且只在旅客流量 ≥j 的车站停车。一名旅客可以从 x 站出发，乘上任意一辆在 x 停车的列车，沿着列车的方向行驶到该列车的下一个停车的车站 y 。如果列车是向左行驶的，即 y<x ，那么旅客需要花费 lx ddtt 币，否则列车是向右行驶的，即 y>x ，此时旅客需要花费 rx ddtt 币。
数据保证对于 1≤i≤n−1 ，有 li≤li+1,ri≥ri+1 。
现有 q 名旅客，依次编号为 1,…,q，旅客 k(1≤k≤q) 的起点是车站 sk，终点是 tk (1≤sk,tk≤n)。假设这些旅客只能靠这条铁路线移动。
对于每名旅客，求这名旅客到达终点至少需要花费多少 ddtt 币。保证同一名旅客的起点与终点不同。允许走回头路。多组测试。
输入格式
第一行一个正整数 T(1≤T≤3⋅104) ，表示数据组数。
接下来对于每组数据，第一行包含两个整数 n,q(1≤n,q≤3⋅105) ，表示车站数量和旅客数量。
第二行包含 n 个整数 a1,…,an ，表示车站的旅客流量。
接下来 n 行，每行两个正整数 li,ri(1≤li,ri≤109,li≤li+1,ri≥ri+1) 。
接下来 q 行，每行两个正整数 sk,tk(1≤sk,tk≤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
数据范围
保证 ∑n,∑q≤3⋅105,1≤li,ri≤109,1≤sk,tk≤n 。
保证 li≤li+1,ri≥ri+1 。
subtask1(3pts)：保证 ∑n≤400 。
subtask2(14pts)：保证 ∑n,∑q≤5000 。
subtask3(21pts)：保证 ∑n≤5000 。
subtask4(20pts)：保证 li=ri=1(1≤i≤n) 。
subtask5(42pts)：无特殊限制。
时间限制：5s
空间限制：1GB