// Author: Ivan Katanic
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long llint;

struct Solution {
  // ax + b(x//2) + c
  llint a, b, c;
};

void AddLeftChildSol(Solution& parent, const Solution& child) {
  parent.a += 2*child.a + child.b;
  parent.c += child.c;
  
}

void AddRightChildSol(Solution& parent, const Solution& child) {
  parent.a += 2*child.a + child.b;
  parent.c += child.c + child.a;
  
}

const int N_MEMO = 15;

Solution memo[N_MEMO + 1][1 << N_MEMO];
int solved[N_MEMO + 1][1 << N_MEMO];
int cookie;

Solution Solve(int n, int a0, int m, int d, bool has_parent) {
  if (n == 1) {
    return Solution{0, 1, 0};
  }

  int size = (1<<n) - 1;
  
  bool should_memo = n <= N_MEMO && has_parent && (a0 + m*d >= size);
  if (should_memo) {
    if (solved[n][a0] == cookie) return memo[n][a0];
  }

  Solution sol{0, 0, 0};

  int first = a0;

  int left_size = (1<<(n-1)) - 1;
  if (first < left_size && m > 0) {
    int nm = min(m, (left_size - first - 1) / d + 1);
    AddLeftChildSol(sol, Solve(n-1, first, nm, d, true));
    first += nm * d;
    m -= nm;
  }
  first -= left_size;

  
  if (!has_parent) {
    if (first == 0 && m > 0) {
      sol.a += 2, sol.c += 1;
      first += d;
      m--;
    }
    first--;
  }


  int right_size = (1<<(n-1)) - 1;
  if (first < right_size && m > 0) {
    int nm = min(m, (right_size - first - 1) / d + 1);
    AddRightChildSol(sol, Solve(n-1, first, nm, d, has_parent));
    first += nm * d;
    m -= nm;
  }
  first -= right_size;
  
  if (has_parent) {
    if (m > 0) {
      sol.b += 1;
    }
  }

  if (should_memo) {
    solved[n][a0] = cookie;
    memo[n][a0] = sol;
  }
  
  return sol;
}

int main(void) {
  int n, q;
  scanf("%d %d", &n, &q);
  while (q--) {
    int a0, m, d;
    scanf("%d %d %d", &a0, &d, &m);
    --a0;

    cookie++;
    Solution sol = Solve(n, a0, m, d, false);
    printf("%lld\n", sol.a + sol.c);
  }
  return 0;
}