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
147
148
149
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>
#define int long long
#define pi pair<int, int>

const int MOD = 1000000007;
using namespace std;

struct event{
  int add;
  int mul;
};

struct sum_range{
  int n;
  vector<int> values;
  sum_range(const vector<event> &content){
    n = content.size();
    values.resize(n+1);
    for(int i=1; i<=n; i++)
      values[i] = values[i-1]+content[i-1].add; //we don't take modulo here on purpose
  }

  int query(int l, int r) { //[l r)
    if(r<=l) return 0;
    r = min(r, n);
    l = max(l, 0LL);
    return values[r]-values[l];
  }
};

int fast_pow(int a, int k){
  //assert(a!=0);
  if(k==0) return 1;
  if(a==0) return 0;
  if(k%2==1) return (a*fast_pow(a, k-1))%MOD;
  if(k%2==0) {
    int value = fast_pow(a, k/2);
    return (value*value)%MOD;
  }
}

int inverse(int a){
  return fast_pow(a, MOD-2);
}

struct mul_range{
  int n;
  vector<int> values;
  mul_range(const vector<event> &content){
    n = content.size();
    values.resize(n+1, 1);
    for(int i=1; i<=n; i++)
      values[i] = (values[i-1]*content[i-1].mul)%MOD; 
  }

  int query(int l, int r) { //[l r)
    if(r<=l) return 1;
    r = min(r, n);
    l = max(l, 0LL);
    return (values[r]*inverse(values[l]))%MOD;
  }
};

  struct effect{
    int multiplier;
    int constant;
  };

struct best_inf_money{
  int n;
  vector<effect> values;

  best_inf_money(const vector<event> & content){
    n = content.size();
    values.resize(n+1, {1, 0});
    for(int i=1; i<=n; i++){
      if(content[i-1].mul == 1){
        values[i] = {values[i-1].multiplier, (values[i-1].constant + content[i-1].add)%MOD};
      } else {
        values[i] = {(content[i-1].mul*values[i-1].multiplier)%MOD, (content[i-1].mul *values[i-1].constant)%MOD};
      }
    }
  }

  effect query(int l, int r){
    if(r<=l) return {1, 0};
    r = min(r, n);
    l = max(l, 0LL);
    auto [a_1, b_1] = values[l];
    auto [a_2, b_2] = values[r];
    int alpha = (a_2 * inverse(a_1))%MOD;
    int beta = (b_2-b_1*alpha);
    beta -= (beta/MOD) * MOD;
    beta += 5 * MOD;
    beta %= MOD;
    return {alpha, beta};
  }
};

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q; cin >> n >> q;
  vector<event> events(n);
  for(auto &[a, m] : events)
    cin >> a >> m;

  set<int> non_trivial;
  for(auto [index, element] : views::enumerate(events))
    if(element.mul != 1)
      non_trivial.insert(index);
  non_trivial.insert(LLONG_MAX);
  
  sum_range add_sum(events);
  mul_range mul_prod(events);
  best_inf_money best_func(events);


  int cnt=0;
  while(q--){
    if(++cnt == 84){
      cerr << "ser";
    }
    int x, l, r; cin >> x >> l >> r;
    //rozwazamy [l, r)
    bool overflowed=false;
    auto next_non_trivial = non_trivial.upper_bound(l-1);
    int result = x;
    int current = l-1;
    while(!overflowed && *next_non_trivial < r){
      result += add_sum.query(current+1, *next_non_trivial);

      auto overflowcheckbeforemod = [&](){
        if(result >= MOD){
          result%=MOD;
          overflowed = true;
        }
      };
overflowcheckbeforemod();
      auto [add, mul] = events[*next_non_trivial];
      if(overflowed || result+add <= result*mul){
        result*=mul;
        overflowcheckbeforemod();
      } else {
        result+=add;
        overflowcheckbeforemod();
      }

      current = *next_non_trivial;
      next_non_trivial = non_trivial.upper_bound(current);
    }
    int non_triv_before_r = *non_trivial.lower_bound(r);
    auto [a, b] = best_func.query(current+1, r);
    ((result*=a)+=b)%=MOD;
    cout << result << '\n';
  }
}