#include <bits/stdc++.h>
#define int long long
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int k, q, a, d, m;
struct zhk {
	ll k, b, y;
	zhk (ll _k = 0, ll _b = 0, ll _y = 0) {
		k = _k;
		b = _b;
		y = _y;
	}
	friend zhk operator + (const zhk& x, const zhk& y) {
		return (zhk) {x.k + y.k, x.b + y.b, x.y + y.y};
	}
	friend zhk& operator += (zhk &x, const zhk& y) {
		return (x = x + y);
	}
} f[2][35][1 << 15];
zhk work(zhk x, int y) {
	return (zhk) {0, x.k * y + x.b, x.y};
}
zhk ls(zhk x) {
	return (zhk) {x.k << 1, x.b, x.y};
}
zhk rs(zhk x) {
	// if (x.y < 1) return (zhk) {x.k << 1, x.b, x.y};
	return (zhk) {x.k << 1, x.b + x.k / 2, x.y};
}
ll calc(ll x, ll y) {
	// cout << x << " " << y << endl;
	bool flag = true;
	zhk ans;
	int z = 1;
	F(i, 1, k - 1) {
		// cout << ans.y << " " << ans.b << " " << z << " " << i + 1 << " " << x << " " << f[0][i + 1][x].k << " " << f[0][i + 1][x].b << " " << f[0][i + 1][x].y << " " << y << endl;
		if ((ans + f[0][i + 1][x]).y <= y) {
			// cout << "! " << f[0][i + 1][x].k << " " << f[0][i + 1][x].b << endl;
			// exit(0);
			ans += work(f[0][i + 1][x], z);
			// cout << i + 1 << " " << ans.b << endl;
			// cout << x << " " << i << " " << k << " " << (1 << (k - i)) - 1 << endl;
			x = ((x - ((1 << (k - i)) - 1)) % d + d) % d;
			// cout << x << endl;
			if (flag) {
				if (ans.y < y && x == 1 % d) ans += (zhk) {0, z * 2 + 1, 1};
				x = (x - 1 + d) % d;//, cout << z * 2 + 1 << endl;
			} else {
				if ((ans + f[flag][i + 1][x]).y <= y) {
					ans += work(f[flag][i + 2][x], z * 2 + 1);
					x = ((x - ((1 << (k - i - 1)) - 1)) % d + d) % d;
					ans += work(f[flag][i + 2][x], z * 2 + 1);
					x = ((x - ((1 << (k - i - 1)) - 1)) % d + d) % d;
					if (x == 1 % d) ans += (zhk) {0, z, 1};
					// cout << ans.b << endl;
					break;
				}
			}
			z = z << 1 | 1;
		} else flag = false, z <<= 1;
	}
	// cout << "ANS: " << ans.b << endl;
	return ans.b;
}
int query(int x) {
	int z = 1;
	bool flag = true;
	F(i, 1, k) {
		// cout << i << " " << x << endl;
		if (flag) {
			if ((1 << (k - i)) == x) return z << 1 | 1;
		} else {
			if ((1 << (k - i + 1)) - 1 == x) return (z >> 1);
		}
		if ((1 << (k - i)) - 1 >= x) {
			z <<= 1;
			flag = false;
		} else {
			x -= (1 << (k - i)) - 1;
			if (flag) x--;
			z = z << 1 | 1;
		}
	}
	assert(0); return -1;
}
signed main() {
	read(k); read(q);
	while (q--) {
		read(a); read(d); read(m);
		if (d <= (1 << 15)) {
			DF(i, k, 1) {
				F(j, 0, d - 1) f[0][i][j] = f[1][i][j] = (zhk) {0, 0, 0};
				// if (i == k) {
				// 	f[0][i][1 % d] = (zhk) {1, 0, 1};
				// 	f[1][i][1 % d] = (zhk) {2, 1, 1};
				// 	continue;
				// }
				if (i != k) {
					F(j, 0, d - 1) {
						// cout << f[0][i + 1][j].y << endl;
						f[0][i][j] += ls(f[0][i + 1][j]);
						f[1][i][j] += ls(f[0][i + 1][j]);
						// if (i == 2) {
						// 	cout << f[0][i + 1][j].k << " " << f[0][i + 1][j].b << " " << f[0][i + 1][j].y << endl;
						// }
						// int t = d;
						// ans += work(f[flag][i + 2][x], z * 2 + 1);
						// x = ((x - ((1 << (k - i - 1)) - 1)) % d + d) % d;
						// if (x == 1 % d) ans += (zhk) {0, z, 1};
						f[0][i][(j + (1 << (k - i)) - 1) % d] += rs(f[0][i + 1][j]);
						// if (i == 2) {
						// 	cout << rs(f[0][i + 1][j]).k << " " << rs(f[0][i + 1][j]).b << " " << rs(f[0][i + 1][j]).y << endl;
						// }
						f[1][i][(j + (1 << (k - i))) % d] += rs(f[1][i + 1][j]);
					}
				}
				// if (i == 3) {
				// 	cout << "! " << f[0][i][0].k << endl;
				// }
				f[0][i][((1 << (k - i + 1)) - 1) % d] += (zhk) {1, 0, 1};
				f[1][i][((1 << (k - i))) % d] += (zhk) {1, 0, 1};
				// cout << i << " " << f[0][i][0].y << endl;
			}
			cout << calc(a % d, (a - 1) / d + m) - calc(a % d, (a - 1) / d) << '\n';
		} else {
			ll ans = 0;
			F(i, 1, m) {
				// cout << a << " " << query(a) << endl;
				ans += query(a);
				a += d;
			} cout << ans << '\n';
		}
	}
	return 0;
}