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
#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define eb emplace_back
#define pb push_back

using ui = uint32_t;
using ll = int64_t;

constexpr ll MOD = 1e9 + 7;

struct TreeNode {
  ll sum = 0, prod = 1;
  static TreeNode combine(TreeNode const& a, TreeNode const& b) {
    return { (a.sum * b.prod + b.sum) % MOD, (a.prod * b.prod) % MOD };
  }
};

// Tak, wiem, że można preprocess suffixów, a potem odpowiedzi O(1), ale lubię drzewka (:
struct SegTree {
  int TREE_BASE;
  vector<TreeNode> tree;
  SegTree(int n, vector<ll> const& add, vector<ll> const& mul) {
    TREE_BASE = (1 << (int(ceil(log2(n)))));
    tree.resize(2 * TREE_BASE);
    for(int i = 1; i <= n; i++) {
      tree[i - 1 + TREE_BASE] = { (mul[i] == 1 ? add[i] : 0), mul[i] };
    }
    for(int i = TREE_BASE - 1; i >= 1; i--) {
      tree[i] = TreeNode::combine(tree[2 * i], tree[2 * i + 1]);
    }
  }
  TreeNode query(int a, int b, int v, int l, int r) {
    if(l >= a && r <= b) {
      return tree[v];
    }
    int mid = (l + r) / 2;
    if(b <= mid) return query(a, b, 2 * v, l, mid);
    else if(a > mid) return query(a, b, 2 * v + 1, mid + 1, r);
    else {
      return TreeNode::combine(
        query(a, b, 2 * v, l, mid),
        query(a, b, 2 * v + 1, mid + 1, r)
      );
    }
  }
  TreeNode query(int a, int b) {
    return query(a, b, 1, 1, TREE_BASE);
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q; cin >> n >> q;

  vector<ll> add(n + 1), mul(n + 1);
  vector<ll> sum(n + 1);

  {
    for(int i = 1; i <= n; i++) {
      cin >> add[i] >> mul[i];
      sum[i] = sum[i - 1] + add[i];
    }
  }

  vector<int> first_gr_one(n + 1);
  first_gr_one[n] = 1e9;

  for(int i = n; i >= 1; i--) {
    if(mul[i] != 1) first_gr_one[i - 1] = i;
    else first_gr_one[i - 1] = first_gr_one[i];
  }

  SegTree st(n, add, mul);

  struct Query {
    ll x, l, r;
    bool is_big = false;
  };

  vector<Query> queries(q);

  for(int q_id = 0; q_id < q; q_id++) {
    auto& [ x, l, r, _ ] = queries[q_id];
    cin >> x >> l >> r;
    int k = l;
    bool x_big = 0;
    while(k < r && !x_big) {
      int i = first_gr_one[k];
      if(i > r) break;
      __int128 res = max(__int128(x + sum[i] - sum[k]), __int128(x + sum[i - 1] - sum[k]) * mul[i]);
      if(res > MOD) {
        x_big = 1;
      }
      x = res % MOD;
      k = i;
    }
    if(x_big && k != r) {
      TreeNode que = st.query(k + 1, r);
      x = TreeNode::combine({ x, 1 }, que).sum;
    }
    else {
      x = (x + sum[r] - sum[k]) % MOD;
    }
    cout << x << '\n';
  }

}