Cumulative Code

A tree is a graph with $n$ nodes and $n-1$ undirected edges in which every pair of nodes is joined by exactly one path. In a labeled tree, each node is labeled with a different integer between $1$ and $n$.

The Prüfer code of a labeled tree is the sequence built by removing nodes one at a time until only two nodes are left. In each step, remove the leaf with the smallest label and append the label of its only neighbour to the end of the code. A leaf is a node with exactly one neighbour. The Prüfer code of a labeled tree is therefore an integer sequence of length $n-2$, and the original tree can be reconstructed from it.

The complete binary tree of depth $k$, written $C_k$, is the labeled tree on $2^k - 1$ nodes in which node $j$ is joined to nodes $2j$ and $2j+1$ for every $j < 2^{k-1}$. Write the Prüfer code of $C_k$ as $p_1, p_2, \ldots, p_{2^k-3}$.

The Prüfer code of $C_k$ can be very long, so you do not print it. Instead, answer $q$ questions about sums of selected elements of the code. Each question consists of three integers $a$, $d$ and $m$, and its answer is $p_a + p_{a+d} + p_{a+2d} + \cdots + p_{a+(m-1)d}$.

The first line contains two integers $k$ and $q$ ($2 \le k \le 30$, $1 \le q \le 300$): the depth of the complete binary tree and the number of questions. Each of the next $q$ lines contains one question as three positive integers $a_j$, $d_j$ and $m_j$, where $a_j$, $d_j$ and $a_j + (m_j - 1)d_j$ are all at most $2^k - 3$.

Print $q$ lines. Line $j$ contains a single integer, the answer to the $j$-th question.

When the Prüfer code of $C_3$ is built, the nodes are removed in the order 4, 5, 2, 1, 6. The Prüfer code of $C_3$ is therefore 2, 2, 1, 3, 3.