CF894D.Ralph And His Tour in Binary Country

Ralph is in the Binary Country. The Binary Country consists of n cities and (n - 1) bidirectional roads connecting the cities. The roads are numbered from 1 to (n - 1), the i-th road connects the city labeled (here ⌊ x⌋ denotes the x rounded down to the nearest integer) and the city labeled (i + 1), and the length of the i-th road is L__i.

Now Ralph gives you m queries. In each query he tells you some city A__i and an integer H__i. He wants to make some tours starting from this city. He can choose any city in the Binary Country (including A__i) as the terminal city for a tour. He gains happiness (H__i - L) during a tour, where L is the distance between the city A__i and the terminal city.

Ralph is interested in tours from A__i in which he can gain positive happiness. For each query, compute the sum of happiness gains for all such tours.

Ralph will never take the same tour twice or more (in one query), he will never pass the same city twice or more in one tour.

拉尔夫身处二进制国家（Binary Country）。该国由 $n$ 座城市和 $(n-1)$ 条双向道路组成，这些道路连接着各城市。道路编号从 $1$ 到 $(n-1)$；其中第 $i$ 条道路连接编号为 $\left\lfloor \frac{i}{2} \right\rfloor$（此处 $\lfloor x \rfloor$ 表示将 $x$ 向下取整）的城市与编号为 $(i+1)$ 的城市，且该道路的长度为 $L_i$。

现在拉尔夫向你提出 $m$ 个询问。在每次询问中，他给出某座城市 $A_i$ 和一个整数 $H_i$。他希望从该城市出发进行若干次旅行。他可以任选二进制国家中的任意一座城市（包括 $A_i$ 自身）作为某次旅行的终点城市。一次旅行带来的幸福值为 $(H_i - L)$，其中 $L$ 表示城市 $A_i$ 与终点城市之间的距离。

拉尔夫只关心那些能带来正幸福值的从 $A_i$ 出发的旅行。对每个询问，请计算所有此类旅行的幸福值之和。

注意：在单次询问中，拉尔夫绝不会重复进行同一条旅行路径；在单次旅行中，他也绝不会重复经过同一座城市。

The first line contains two integers n and m (1 ≤ n ≤ 106, 1 ≤ m ≤ 105).

(n - 1) lines follow, each line contains one integer L__i (1 ≤ L__i ≤ 105), which denotes the length of the i-th road.

m lines follow, each line contains two integers A__i and H__i (1 ≤ A__i ≤ n, 0 ≤ H__i ≤ 107).

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^6$，$1 \le m \le 10^5$）。

接下来 $n-1$ 行，每行包含一个整数 $L_i$（$1 \le L_i \le 10^5$），表示第 $i$ 条道路的长度。

接下来 $m$ 行，每行包含两个整数 $A_i$ 和 $H_i$（$1 \le A_i \le n$，$0 \le H_i \le 10^7$）。

Print m lines, on the i-th line print one integer — the answer for the i-th query.

输出 m 行，第 i 行输出一个整数——即第 i 个查询的答案。

Here is the explanation for the second sample.

Ralph's first query is to start tours from city 2 and H__i equals to 4. Here are the options:

• He can choose city 5 as his terminal city. Since the distance between city 5 and city 2 is 3, he can gain happiness 4 - 3 = 1.
• He can choose city 4 as his terminal city and gain happiness 3.
• He can choose city 1 as his terminal city and gain happiness 2.
• He can choose city 3 as his terminal city and gain happiness 1.
• Note that Ralph can choose city 2 as his terminal city and gain happiness 4.
• Ralph won't choose city 6 as his terminal city because the distance between city 6 and city 2 is 5, which leads to negative happiness for Ralph.

So the answer for the first query is 1 + 3 + 2 + 1 + 4 = 11.

以下是第二个样例的解释。

拉尔夫的第一个查询是：从城市 2 出发开始旅行，且 H__i = 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$。