[CERC2017] Cumulative Code

给一棵深度为 $k$，点数为 $2^k-1$ 的完全二叉树，其中根节点编号为 $1$，节点 $x$ 的儿子为 $2x$ 和 $2x+1$。 记它的 prufer 序列为 $p$，下标从 $1$ 开始。给定 $q$ 次询问，每次给出三个参数 $a$、$d$、$m$，求 $\sum\limits_{i=0}^{m-1}p_{a+id}$。

As you probably know, a tree is a graph consisting of $n$ nodes and $n - 1$ undirected edges in which any two nodes are connected 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 a unique sequence associated with the tree, generated by repeatedly removing nodes from the tree until only two nodes remain. More precisely, in each step we remove the leaf with the smallest label and append the label of its neighbour to the end of the code. Recall, a leaf is a node with exactly one neighbour. Therefore, the Prüfer code of a labeled tree is an integer sequence of length $n - 2$. It can be shown that the original tree can be easily reconstructed from its Prüfer code. The complete binary tree of depth $k$, denoted with $C_k$, is a labeled tree with $2^k - 1$ nodes where node $j$ is connected to nodes $2j$ and $2j + 1$ for all $j < 2^{k-1}$. Denote the Prüfer code of $C_k$ with $p_1,p_2,..., p_{2^k-3}$. Since the Prüfer code of $C_k$ can be quite long, you do not have to print it out. Instead, you need to answer $n$ questions about the sums of certain elements on the code. Each question consists of three integers: $a, d$ and $m$. The answer is the sum of the of the $C_k'$ s Prüfer code elements $p_a, p_{a+d},p_{a+2d},...,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. The $j-th$ of the following $q$ lines contains the $j-th$ question:three positive integers $a_j,d_j$ and $m_j$ such that $a_j,d_j$ and $a_j + (m_j - 1)d_j$ are all at most $2^k - 3$.

Output 1 lines. The $j-th$ line should contain a single integer — the answer to the $j-th$ question.

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

2
2
1
3
3

4 4
2 1 5
4 4 3
4 8 1
10 3 2

18
15
5
13

7 1
1 1 125

4031

In the first example above, when constructing the Prüfer code for $C_3$ the nodes are removed in the following order: $4, 5, 2, 1, 6$. Therefore, the Prüfer code of $C_3$ is $2, 2, 1, 3, 3$.