众所周知，树是一个由 $n$ 个节点和 $n-1$ 条无向边组成的图，其中任意两个节点之间都有且仅有一条路径。在标记树中，每个节点都被赋予一个 $1$ 到 $n$ 之间的不同整数作为标签。

标记树的 Prüfer 序列是与该树相关联的唯一序列，通过重复从树中移除节点直到只剩下两个节点来生成。更具体地说，在每一步中，我们移除标签最小的叶子节点，并将该叶子节点的邻居标签追加到序列末尾。回想一下，叶子节点是只有一个邻居的节点。因此，标记树的 Prüfer 序列是一个长度为 $n-2$ 的整数序列。可以证明，原始树可以很容易地从其 Prüfer 序列中重构出来。

深度为 $k$ 的完全二叉树（记为 $C_k$）是一棵拥有 $2^k-1$ 个节点的标记树，其中对于所有 $j < 2^{k-1}$，节点 $j$ 与节点 $2j$ 和 $2j+1$ 相连。记 $C_k$ 的 Prüfer 序列为 $p_1, p_2, \dots, p_{2^k-3}$。

由于 $C_k$ 的 Prüfer 序列可能非常长，你不需要将其打印出来。相反，你需要回答 $n$ 个关于序列中某些元素之和的问题。每个问题包含三个整数：$a$、$d$ 和 $m$。答案是 $C_k$ 的 Prüfer 序列中元素 $p_a, p_{a+d}, p_{a+2d}, \dots, p_{a+(m-1)d}$ 的总和。

输入格式

第一行包含两个整数 $k$ 和 $q$ ($2 \le k \le 30, 1 \le q \le 300$)，分别表示完全二叉树的深度和问题的数量。接下来的 $q$ 行中，第 $j$ 行包含第 $j$ 个问题：三个正整数 $a_j, d_j$ 和 $m_j$，满足 $a_j, d_j$ 以及 $a_j + (m_j - 1)d_j$ 均不超过 $2^k - 3$。

输出格式

输出 $q$ 行。第 $j$ 行应包含一个整数，即第 $j$ 个问题的答案。

样例

样例输入 1

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

样例输出 1

2
2
1
3
3

样例输入 2

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

样例输出 2

18
15
5
13

样例输入 3

7 1
1 1 125

样例输出 3

4031

说明

在上面的第一个样例中，构造 $C_3$ 的 Prüfer 序列时，节点移除的顺序为：4, 5, 2, 1, 6。因此，$C_3$ 的 Prüfer 序列为 2, 2, 1, 3, 3。