Prufer Code Queries on a Complete Binary Tree

A tree is a connected graph with no cycles. In a labeled tree with n nodes there are exactly n - 1 undirected edges such that every node has a unique label among {1, 2, ..., n}. The Prüfer code of a labeled tree is a unique sequence of length \(n-2\) obtained by repeatedly removing the leaf (a node with degree 1) having the smallest label and appending its only neighbor to the sequence, until only two nodes remain.

The complete binary tree of depth \(k\), denoted by \(C_k\), is a labeled tree with \(2^k - 1\) nodes. It is constructed such that for each node \(j < 2^{k-1}\), its left child is \(2j\) and its right child is \(2j+1\). Let its Prüfer code be \(p_1, p_2, \ldots, p_{2^k-3}\).

In this problem, you are given the depth \(k\) of the tree and a series of queries. Each query is represented by three integers: \(a\), \(d\), and \(m\). For each query, you are to calculate the sum of the subsequence \(p_a, p_{a+d}, p_{a+2d}, \ldots, p_{a+(m-1)d}\) from the Prüfer code.

inputFormat

The input begins with a line containing two integers \(k\) and \(q\), where \(k\) (with \(k \ge 2\)) is the depth of the complete binary tree \(C_k\) and \(q\) is the number of queries.

The next \(q\) lines each contain three integers \(a\), \(d\), and \(m\) describing one query. It is guaranteed that the query parameters are valid (i.e. \(a+(m-1)d \le 2^k-3\)).

outputFormat

For each query, output a single line containing the computed sum from the corresponding subsequence of the Prüfer code.

sample

3 3
1 1 2
2 1 1
1 2 1

3
4
2