问题描述
Bestland有一条非常长的马路，马路上设有\(n\)个公交汽车站。公交汽车站从左到右标号为1到\(n\)。有\(m\)个人想要乘公交。你的任务是找出每个人到终点为止所需要的时间。注意：你需要用来解决这道题目的信息在Input里面，请仔细阅读。
输入描述
输入的第一行包含一个整数\(T\ (1 \le T \le 60)\)，表示测试数据的组数。对于每组测试数据：第一行包含两个整数\(n\)和\(m\) \((2 \le n, m \le 10^5)\)，表示公交车站的数目和乘客的数目。 接下来一行包含\(n - 1\)个整数, \(d_1, d_2, \dots, d_{n-1}\) (\(1 \le d_i \le 10^9\)). \(d_i\)表示第\(i\)个公交站和第\(i + 1\)个公交站之间的距离。在接下来的\(m\)行, 每行包含两个整数\(x_i\)和\(y_i\) (\(1 \le x_i, y_i \le n, x_i \ne y_i\)), 表示第\(i\)个人时刻0的时候在第\(x_i\)个公交站并且想要到第\(y_i\)个公交站去。\((1 \le i \le m)\)
对于第\(i\)个人, 公交车在第\(((i - 1)\text{ mod } n) + 1\)个公交站点在时刻0的时候，并且公交一开始往右开。公交到达站点\(n\)的时候会立刻转向往左开，同样当公交到达站点1的时候也会立刻转向往右开。你可以认为公交每秒只开一个单位距离，你只需要考虑公交开的时间。
输出描述
对于每个人，输出到达\(y_i\)个公交站点需要的最少时间。
输入样例
1
7 3
2 3 4 3 4 5
1 7
4 5
5 4
输出样例
21
10
28
提示：
对于第一个人, 公交在站点1出发, 然后这个人在时刻0上车。21秒之后，公交到达站点7。
对于第二个人，公交在站点2出发。7秒之后，公交到达站点4，这个人上车。之后又过了3秒，公交到达站点5.总共用了10秒。
对于第三个人，公交在站点3出发。7秒之后，公交到达站点5，这个人上车。之后过了9秒，公交达到站点7，然后转向开往站点0。之后经过12秒，公交达到站点4。因此总共需要28秒时间。
