{"raw_statement":[{"iden":"statement","content":"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_.\n\nNow 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.\n\nRalph 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.\n\nRalph 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."},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 106, 1 ≤ _m_ ≤ 105).\n\n(_n_ - 1) lines follow, each line contains one integer _L__i_ (1 ≤ _L__i_ ≤ 105), which denotes the length of the _i_\\-th road.\n\n_m_ lines follow, each line contains two integers _A__i_ and _H__i_ (1 ≤ _A__i_ ≤ _n_, 0 ≤ _H__i_ ≤ 107)."},{"iden":"output","content":"Print _m_ lines, on the _i_\\-th line print one integer — the answer for the _i_\\-th query."},{"iden":"examples","content":"Input\n\n2 2\n5\n1 8\n2 4\n\nOutput\n\n11\n4\n\nInput\n\n6 4\n2\n1\n1\n3\n2\n2 4\n1 3\n3 2\n1 7\n\nOutput\n\n11\n6\n3\n28"},{"iden":"note","content":"Here is the explanation for the second sample.\n\nRalph's first query is to start tours from city 2 and _H__i_ equals to 4. Here are the options:\n\n*   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.\n*   He can choose city 4 as his terminal city and gain happiness 3.\n*   He can choose city 1 as his terminal city and gain happiness 2.\n*   He can choose city 3 as his terminal city and gain happiness 1.\n*   Note that Ralph can choose city 2 as his terminal city and gain happiness 4.\n*   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.\n\nSo the answer for the first query is 1 + 3 + 2 + 1 + 4 = 11."}],"translated_statement":[{"iden":"statement","content":"Ralph 在 Binary Country 中。Binary Country 由 #cf_span[n] 座城市和 #cf_span[(n - 1)] 条双向道路组成，这些道路连接着城市。道路编号从 #cf_span[1] 到 #cf_span[(n - 1)]，第 #cf_span[i] 条道路连接编号为 #cf_span[⌊ i/2 ⌋] 的城市（此处 #cf_span[⌊ x⌋] 表示将 #cf_span[x] 向下取整到最近的整数）和编号为 #cf_span[(i + 1)] 的城市，且第 #cf_span[i] 条道路的长度为 #cf_span[Li]。\n\n现在 Ralph 给你 #cf_span[m] 个查询。在每个查询中，他告诉你某个城市 #cf_span[Ai] 和一个整数 #cf_span[Hi]。他希望从这个城市出发进行一些旅行。他可以选择 Binary Country 中的任意城市（包括 #cf_span[Ai]）作为旅行的终点城市。在一次旅行中，他获得的幸福值为 #cf_span[(Hi - L)]，其中 #cf_span[L] 是城市 #cf_span[Ai] 与终点城市之间的距离。\n\nRalph 对那些能获得正幸福值的旅行感兴趣。对于每个查询，计算所有此类旅行的幸福值总和。\n\nRalph 在一次查询中不会重复进行相同的旅行，也不会在一次旅行中经过同一城市两次或以上。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 106]，#cf_span[1 ≤ m ≤ 105]）。\n\n接下来 #cf_span[(n - 1)] 行，每行包含一个整数 #cf_span[Li]（#cf_span[1 ≤ Li ≤ 105]），表示第 #cf_span[i] 条道路的长度。\n\n接下来 #cf_span[m] 行，每行包含两个整数 #cf_span[Ai] 和 #cf_span[Hi]（#cf_span[1 ≤ Ai ≤ n]，#cf_span[0 ≤ Hi ≤ 107]）。\n\n请输出 #cf_span[m] 行，第 #cf_span[i] 行输出一个整数 —— 第 #cf_span[i] 个查询的答案。\n\n以下是第二个样例的解释。\n\nRalph 的第一个查询是从城市 #cf_span[2] 出发，且 #cf_span[Hi] 等于 #cf_span[4]。可能的选择如下：\n\n因此第一个查询的答案是 #cf_span[1 + 3 + 2 + 1 + 4 = 11]。\n\n"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 106]，#cf_span[1 ≤ m ≤ 105]）。#cf_span[(n - 1)] 行随后出现，每行包含一个整数 #cf_span[Li]（#cf_span[1 ≤ Li ≤ 105]），表示第 #cf_span[i] 条道路的长度。#cf_span[m] 行随后出现，每行包含两个整数 #cf_span[Ai] 和 #cf_span[Hi]（#cf_span[1 ≤ Ai ≤ n]，#cf_span[0 ≤ Hi ≤ 107]）。"},{"iden":"output","content":"请输出 #cf_span[m] 行，第 #cf_span[i] 行输出一个整数 —— 第 #cf_span[i] 个查询的答案。"},{"iden":"examples","content":"输入2 251 82 4输出114输入6 4211322 41 33 21 7输出116328"},{"iden":"note","content":"以下是第二个样例的解释。\nRalph 的第一个查询是从城市 #cf_span[2] 出发，且 #cf_span[Hi] 等于 #cf_span[4]。可能的选择如下：\n他可以选择城市 #cf_span[5] 作为终点。由于城市 #cf_span[5] 与城市 #cf_span[2] 之间的距离为 #cf_span[3]，他可以获得幸福值 #cf_span[4 - 3 = 1]。\n他可以选择城市 #cf_span[4] 作为终点，获得幸福值 #cf_span[3]。\n他可以选择城市 #cf_span[1] 作为终点，获得幸福值 #cf_span[2]。\n他可以选择城市 #cf_span[3] 作为终点，获得幸福值 #cf_span[1]。\n注意，Ralph 可以选择城市 #cf_span[2] 作为终点，获得幸福值 #cf_span[4]。\nRalph 不会选择城市 #cf_span[6] 作为终点，因为城市 #cf_span[6] 与城市 #cf_span[2] 之间的距离为 #cf_span[5]，这会导致他的幸福值为负。\n因此第一个查询的答案是 #cf_span[1 + 3 + 2 + 1 + 4 = 11]。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ T $ be a rooted binary tree with $ n $ nodes labeled $ 1 $ to $ n $, where node $ i $ (for $ 2 \\leq i \\leq n $) is connected to node $ \\lfloor i/2 \\rfloor $ by an edge of length $ L_{i-1} $. The tree is rooted at node 1.\n\nFor each query $ (A_i, H_i) $, define the set of valid terminal cities as:\n$$\nS_i = \\{ v \\in \\{1, 2, \\dots, n\\} \\mid d(A_i, v) < H_i \\}\n$$\nwhere $ d(u, v) $ denotes the unique path distance between nodes $ u $ and $ v $ in the tree.\n\nThe happiness gained for a tour from $ A_i $ to terminal city $ v $ is $ H_i - d(A_i, v) $.\n\nThe answer for query $ i $ is:\n$$\n\\sum_{v \\in S_i} (H_i - d(A_i, v))\n$$\n\nEquivalently:\n$$\n|S_i| \\cdot H_i - \\sum_{v \\in S_i} d(A_i, v)\n$$\n\nCompute this for each query $ i = 1, 2, \\dots, m $.","simple_statement":null,"has_page_source":false}