Binary Tree Query on Distance-Constrained Nodes

Given a full binary tree with \(2^n - 1\) nodes. The weight of node \(i\) is \(w_i\), and node \(1\) is the root. For each non-root node \(i\), there is an undirected edge connecting node \(i\) and node \(\left\lfloor \frac{i}{2} \right\rfloor\). The distance between two nodes \(u\) and \(v\) is defined as the minimum number of edges on the path joining them.

You are given \(m\) queries. In the \(i\)-th query, three positive integers \(x_i\), \(y_i\), and \(k_i\) are provided. For each query, output the sum of weights of all nodes whose distance to both node \(x_i\) and node \(y_i\) does not exceed \(k_i\).

Note: \(\left\lfloor X \right\rfloor\) denotes the greatest integer less than or equal to \(X\).

inputFormat

The first line contains two integers \(n\) and \(m\), where the tree has \(2^n - 1\) nodes and there are \(m\) queries.

The second line contains \(2^n - 1\) integers \(w_1, w_2, \ldots, w_{2^n-1}\) representing the weights of the nodes in order.

Each of the next \(m\) lines contains three integers \(x_i\), \(y_i\), and \(k_i\) for the \(i\)-th query.

outputFormat

For each query, output a single integer — the sum of the weights of all nodes that satisfy the condition.

sample

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

4
1
6