Problem Background

I came. I saw. I had anxiety. I left.

Problem Description

Given a binary tree with $2^n-1$ nodes, where the weight of node $i$ is $w_i$, and node $1$ is the root node. For all non-root nodes $i$, there is a bidirectional edge connecting node $i$ and node $\left\lfloor \frac{i}{2} \right\rfloor$. Note that $\left\lfloor X \right\rfloor$ represents the largest integer not greater than $X$.

Define the distance between nodes $u$ and $v$ as the minimum number of edges needed to traverse from node $u$ to node $v$. Given $m$ queries, each query provides three positive integers $x_i, y_i, k_i$. You need to output the sum of the weights of the nodes in the tree that are within a distance of $k_i$ from both nodes $x_i$ and $y_i$.

Input Format

The first line contains two positive integers $n$ and $m$.

The second line contains $2^n-1$ positive integers, where the $i$-th integer is $w_i$.

The next $m$ lines, each containing three positive integers $x_i, y_i, k_i$.

Output Format

Output $m$ lines, each line containing an integer representing the answer to the $i$-th query.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2
7
3

Sample Input #2

4 5
3 4 10 7 1 6 10 6 16 5 3 16 6 2 9
1 4 6
4 2 1
1 14 5
6 13 3
11 15 2

Sample Output #2

104
11
74
51
0

Notes

「Sample Explanation #1」

For the first query, the nodes that meet the condition are $1, 2$, and the sum of their weights is $2$.

For the second query, the nodes that meet the condition are $1, 2, 3, 4, 5, 6, 7$, and the sum of their weights is $7$.

For the third query, the nodes that meet the condition are $1, 2, 3$, and the sum of their weights is $3$.

「Data Range」

For $100\%$ of the data, $2 \leq n \leq 18$, $1 \leq m \leq 2 \times 10^5$, $1 \leq x_i, y_i \leq 2^n-1$, $1 \leq k_i \leq 10^9$, $1 \leq w_i \leq 10^9$, $x_i \neq y_i$. The node numbers range from $1$ to $2^n-1$.

见题面 Input 部分

见题面 Output 部分