1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <bits/stdc++.h>
#define ll long long
#define debug if (0)

const int MAX_N = 5e5;
const ll MOD = 1e9 + 7;
ll a[MAX_N + 3];
ll b[MAX_N + 3];

int n, q;

ll pref_sum[MAX_N + 3];
int next_2_mul[MAX_N + 3];

// for the segment tree
const ll BASE = 1 << 19;
std::pair<ll, ll> tree[2 * BASE + 5];

void insert(int i, int lo, int hi, int v, ll ap, ll bp) {
  if (i < lo || i > hi || lo > hi)
    return;
  if (lo == hi) {
    tree[v] = {ap, bp};
    return;
  }
  int mid = (lo + hi) / 2;
  if (i <= mid)
    insert(i, lo, mid, v * 2, ap, bp);
  else
    insert(i, mid + 1, hi, v * 2 + 1, ap, bp);

  tree[v] = {
      (tree[v * 2 + 1].first * tree[v * 2].first) % MOD,
      (tree[v * 2 + 1].first * tree[v * 2].second + tree[v * 2 + 1].second) %
          MOD};
}

std::pair<ll, ll> query(int L, int R, int lo, int hi, int v) {
  if (L > R || lo > hi || R < lo || L > hi)
    return {1, 0};
  if (lo >= L && hi <= R) {
    return tree[v];
  }
  int mid = (lo + hi) / 2;

  auto [a1, b1] = query(L, R, lo, mid, v * 2);
  auto [a2, b2] = query(L, R, mid + 1, hi, v * 2 + 1);

  return {(a2 * a1) % MOD, (a2 * b1 + b2) % MOD};
}

void preprocess() {
  // pref_sum
  pref_sum[0] = 0;
  for (int i = 1; i <= n; i++)
    pref_sum[i] = pref_sum[i - 1] + b[i];

  // next_2_mul
  int last_2_mul = -1;
  for (int i = n; i >= 1; i--) {
    if (a[i] >= 2)
      last_2_mul = i;
    next_2_mul[i] = last_2_mul;
  }

  // build the tree
  for (int i = 1; i <= n; i++)
    if (a[i] == 1)
      insert(i, 1, n, 1, 1, b[i]);
    else
      insert(i, 1, n, 1, a[i], 0);
}

// NOT modulo!
ll sum(int l, int r) {
  if (l > r)
    return 0;
  return pref_sum[r] - pref_sum[l - 1];
}

ll query(ll x, int l, int r) {
  int ROUNDS = 32;
  int i = l + 1;
  bool above_max = false;

  for (int round = 1; round <= ROUNDS;
       round++) { // after one round, result should be twice as large
    if (i > r)
      break;

    // add until next mul by >= 2
    int j = next_2_mul[i];

    if (j == -1 || j > r) {
      // just adding till the end
      x = (x + sum(i, r)) % MOD;
      i = r + 1;
      break;
    } else {
      x += sum(i, j - 1);

      i = j;

      if (x >= MOD) {
        above_max = true;
        break;
      }
    }

    // add or multiply
    assert(a[i] >= 2);

    if (above_max || x * a[i] >= x + b[i])
      x = (x * a[i]) % MOD;
    else
      x = (x + b[i]) % MOD;

    i++;
  }

  x %= MOD;

  // in the end, apply optimal suffix, if anything is left
  if (i <= r) {
    auto [ap, bp] = query(i, r, 1, n, 1);
    x = (ap * x + bp) % MOD;
  }

  return x;
}

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(NULL);
  std::cin >> n >> q;
  for (int i = 1; i <= n; i++)
    std::cin >> b[i] >> a[i];

  preprocess();

  while (q--) {
    ll x, l, r;
    std::cin >> x >> l >> r;
    std::cout << query(x, l, r) << "\n";
  }
}