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

#define int long long
#define ll long long
#define ld long double

#define endl '\n'
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x),end(x)
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define ROF(i,r,l) for(int i=(r);i>=(l);i--)

#define _$ auto operator<<(auto&o,auto x)->decltype
_$(x.st,o){return o<<"("<<x.st<<", "<<x.nd<<")";}
_$(end(x),o){o<<"{";for(int i=0;auto e:x)o<<","+!i++<<e;return o<<"}";}

#ifdef LOCAL
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){\
  ((cerr<<$<<"; "),...)<<'\n';}(x)
#else
#define debug(...)
#endif

#define rep(i,a,b) for(int i=(a);i<(b); i++)
using pii=pair<int,int>;
using vi=vector<int>;

const int inf = 1e9+7;
const int N = 5e5 + 7;
const int T = 1 << 19;
const int M = 1e9 + 7;

pii tree[T << 1];

pii operator+ (pii a, pii b) {
  return {a.st*b.st%M, (a.nd*b.st+b.nd)%M};
}

pii query(int l, int r) {
  pii L{1, 0}, R{1, 0};
  for (l += T, r += T + 1; l < r; l >>= 1, r >>= 1) {
    if (l & 1)  L = L + tree[l++];
    if (r & 1)  R = tree[--r] + R;
  }
  return L + R;
}

int n, q, a[N], b[N], nxt[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> q;
  FOR(i,1,n){
    cin>>a[i]>>b[i];

    if (b[i] > 1) {
      tree[i+T]={b[i],0};
    } else {
      tree[i+T]={1,a[i]};
    }
    a[i]+=a[i-1]; 
  }
  
  nxt[n+1]=n+1;
  ROF(i,n,1){
    if (b[i] >= 2){
      nxt[i]=i;
    } else {
      nxt[i] = nxt[i+1];
    }
  }

  ROF(i,T-1,1){
    tree[i]=tree[i<<1|0]+tree[i<<1|1];
  }
 
  FOR(i,1,q){
    int x,l,r;
    cin >> x >> l >> r;
    l++;

    // debug("Query",x,l,r);
    while (x < M && l <= r) {
      if (nxt[l] > r) {
        x += a[r] - a[l - 1];
        l = r + 1;
        break;
      }

      x += a[nxt[l] - 1] - a[l - 1];
      //debug("adding:", a[nxt[l]-1] - a[l-1]);
      l = nxt[l];
      if (x < M) {
        if (x * b[l] > x + a[l]-a[l-1]) {
          x *= b[l];
        } else {
          x += a[l]-a[l-1];
        }
        l++;
      }
    }

    x %= M;
    
    if (l <= r) {
      auto [A,B] = query(l,r);
      //debug(l,r,A,B);

      x = ((A * x % M) + B) % M;
    }

    cout << x << '\n';
  }
  return 0;
}