拉尔夫在二元国家。二元国家由 n 个城市和连接城市的 (n - 1) 条双向道路组成。道路编号从 1 到 (n - 1),第 i 条道路连接标记为 $$\left\lfloor \frac{i+1}{2} \right\rfloor$$ 的城市(这里 ⌊ x⌋ 表示 x 向下舍入到最接近的整数)和标记为 (i + 1) 的城市,第 i 条道路的长度为 Li。
现在拉尔夫给你 m 个疑问。在每个查询中,他都会告诉您一些城市 Ai 和一个整数 Hi。他想从这座城市出发进行一些旅行。他可以选择二元国的任意一个城市(包括艾城)作为游览的终点城市。他在一次旅行中获得了幸福感(Hi - L),其中L是城市Ai与终点城市之间的距离。
拉尔夫对来自艾城的旅行很感兴趣,在旅行中他可以获得积极的快乐。对于每个查询,计算所有此类旅行的幸福感增益总和。
拉尔夫永远不会在同一个旅行中两次或多次(在一个查询中),他永远不会在一次旅行中两次或多次经过同一个城市。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 106, 1 ≤ m ≤ 105)。
接下来有 (n - 1) 行,每行包含一个整数 Li (1 ≤ Li ≤ 105),表示第 i 条路的长度。
m 行,每行包含两个整数 Ai 和 Hi (1 ≤ Ai ≤ n, 0 ≤ Hi ≤ 107)。
输出
打印 m 行,在第 i 行打印一个整数——第 i 个查询的答案。
示例
输入 #1
2 2 5 1 8 2 4
输出 #1
11 4
输入 #2
6 4 2 1 1 3 2 2 4 1 3 3 2 1 7
输出 #2
11 6 3 28
注意
这是第二个示例的说明。
Ralph 的第一个查询是从城市 2 开始游览,Hi 等于 4。以下是选项:
- 他可以选择城市 5 作为他的终端城市。由于城市5与城市2的距离为3,因此他可以获得的幸福感为4 - 3 = 1。
- 他可以选择城市4作为他的终点城市并获得幸福3。
- 他可以选择城市1作为他的终点城市并获得幸福2。
- 他可以选择城市3作为他的终点城市并获得幸福1。
- 请注意,拉尔夫可以选择城市 2 作为他的终点城市并获得幸福 4。
- 拉尔夫不会选择城市6作为他的终点城市,因为城市6和城市2之间的距离是5,这会导致拉尔夫的幸福感为负。
因此第一个查询的答案是 1 + 3 + 2 + 1 + 4 = 11。