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$。你的任务是为每名游客找到行程的最小费用。

保证对于每个 $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$）。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$，其中 $a_i$ 是车站 $i$ 的重要性（$1 \le a_i \le n$）。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$：在车站 $i$ 的费用（$1 \le l_i, r_i \le 10^9$，$l_i \le l_{i+1}$，$r_i \ge r_{i+1}$）。

接下来 $q$ 行，第 $j$ 行包含两个整数 $s_j$ 和 $t_j$：第 $j$ 名游客行程的起点和终点（$1 \le s_j, t_j \le n$）。

所有测试用例中 $n$ 的总和与 $q$ 的总和均不超过 $3 \cdot 10^5$。

输出格式

对于每名游客，输出一行答案。

样例

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