你好！我是你的OI金牌教练。

我们继续“历史+编程”的跨学科训练。这次我们将目光投向隋唐时期，以伟大的京杭大运河与古代的漕运制度为背景。

这道题目是为 GESP 6级 设计的。 GESP 6级相比5级，除了对逻辑实现有要求外，开始强调算法效率和时间复杂度优化。你需要掌握前缀和 (Prefix Sum) 这一重要的算法技巧，将 $O(N)$ 的查询优化为 $O(1)$。

第一部分：背景知识讲解

1. 隋唐大运河 (The Grand Canal)

隋炀帝杨广为了加强南北交通，巩固统治，开凿了以洛阳为中心，北达涿郡（今北京），南至余杭（今杭州）的大运河。它是世界上里程最长、工程最大的古代运河。

2. 漕运制度 (Grain Transport System)

中国古代政治中心（京城）多在北方，但经济重心和粮食产区逐渐南移（“苏湖熟，天下足”）。为了维持京城的朝廷消耗和军队给养，朝廷需要通过运河将南方的粮食（称为“漕粮”）长途运输到北方。这种制度称为漕运。

3. 关卡与消耗

漕运路途遥远，沿途经过不同的河段。有的河段水流平缓，运输成本低；有的河段水流湍急或需要通过船闸（如著名的“堰”），运输成本高昂。 作为户部（掌管财政）的官员，需要快速计算出从一个城市运送到另一个城市的总路费成本，以便核算预算。

第二部分：题目内容

题目名称：漕运成本 (Canal Transport Cost)

题目描述

隋唐大运河连接了 $N$ 座繁华的城市，我们将这些城市顺次编号为 $1$ 到 $N$（从北向南排列）。

这就意味着，城市之间共有 $N-1$ 段河道。具体来说，第 $i$ 段河道连接了城市 $i$ 和城市 $i+1$。 由于水流、风向和过闸费用的不同，每一段河道的单次通行成本是不同的。我们用 $W_i$ 表示第 $i$ 段河道（即城市 $i$ 到 $i+1$）的通行成本。

现在，户部尚书下达了 $M$ 条漕运指令。第 $j$ 条指令要求将一批物资从城市 $u_j$ 运送到城市 $v_j$。 请注意：

1. 方向无关性：为了简化计算，我们假设逆流和顺流的成本是一样的，即从 $i$ 到 $i+1$ 的成本等于从 $i+1$ 到 $i$ 的成本，均为 $W_i$。
2. 区间累加：从城市 $u$ 到城市 $v$ 的总成本，等于沿途所有经过的河段成本之和。

由于 $N$ 和 $M$ 的数值可能非常大，如果对每次指令都逐段累加计算，可能会延误军机（程序超时）。请你编写一个高效的程序，快速计算出每一次漕运指令的总成本。

输入格式

第一行包含两个正整数 $N, M$。

• $N$ 表示城市数量。
• $M$ 表示漕运指令的数量。

第二行包含 $N-1$ 个正整数 $W_1, W_2, \dots, W_{N-1}$，用空格隔开。

• $W_i$ 表示城市 $i$ 和城市 $i+1$ 之间的河道通行成本。

接下来 $M$ 行，每行包含两个正整数 $u, v$。

• 表示一次从城市 $u$ 运送到城市 $v$ 的指令。
• 注意：可能 $u < v$（南下），也可能 $u > v$（北上），甚至 $u = v$（成本为0）。

输出格式

输出 $M$ 行，每行一个整数，表示对应指令的总成本。

输入输出样例 #1

输入：

5 3
2 5 1 4
1 3
4 2
1 5

输出：

7
6
12

样例 #1 解释： 共有 5 个城市，4 段河道：

• 河段1 (1-2): 2
• 河段2 (2-3): 5
• 河段3 (3-4): 1
• 河段4 (4-5): 4

查询 1: 从 1 到 3。经过河段 1, 2。成本 $2 + 5 = 7$。 查询 2: 从 4 到 2。经过河段 3, 2。成本 $1 + 5 = 6$。 查询 3: 从 1 到 5。经过所有河段。成本 $2 + 5 + 1 + 4 = 12$。

数据范围

对于 $100\%$ 的数据：

• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le W_i \le 10^4$
• $1 \le u, v \le N$
• 保证答案在 long long 范围内。