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

using namespace std;

#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pi; 
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;

const ll mod = 1e9+7;
const ll max_n = 5e5+7;

ll a[max_n];
ll b[max_n];

ll next_mult[max_n]; //nastepny po nas!
ll mult_suf[max_n];
ll pref_a[max_n]; //suma na prefixie!
ll a_mult[max_n]; //na suffixie

ll get_pot(ll a, ll b){
    if(b == 0) return 1;
    ll val = get_pot(a,b/2);
    ll ans = (val*val)%mod;
    if(b%2 == 1) ans = (ans*a)%mod;
    return ans;
}

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n,q; cin >> n >> q;
    rep(i,1,n){
        cin >> a[i] >> b[i];
        pref_a[i] = (pref_a[i-1]+a[i])%mod;
        //cout << "i: " << i << " pref_a: " << pref_a[i] << '\n';
    }
    
    next_mult[n+1] = n+1;
    mult_suf[n+1] = 1;

    irep(i,n,1){
        mult_suf[i] = (mult_suf[i+1]*b[i])%mod;
        next_mult[i] = (b[i+1] > 1 ? i+1 : next_mult[i+1]);
        a_mult[i] = a_mult[i+1];
        if(b[i] == 1) a_mult[i] += a[i]*mult_suf[i+1];
        a_mult[i] %= mod;
        //cout << "i: " << i << " next_mult: " << next_mult[i] << " mult_suf: " << mult_suf[i]
        //     << " a_mult: " << a_mult[i] << " pref_a: " << pref_a[i] << '\n';
    }

    while(q--){
        ll x,l,r;
        cin >> x >> l >> r;
        l++;
        //cout << "\nx: " << x << " l: " << l << " r: " << r << '\n'; 
        while(x < mod){
            x %= mod;
            x = max(x+a[l],x*b[l]);
            ll n = next_mult[l];
            //cout << "x: " << x << " n: " << n << '\n';
            if(n > r){
                x += pref_a[r]-pref_a[l]+mod;
                l = r+1;
                break;
            }
            x += pref_a[n-1]-pref_a[l];
            if(pref_a[n-1]-pref_a[l] < 0) x += mod;
            l = n;
        }
        x %= mod;

        if(l > r){
            cout << x << '\n';
            continue;
        }

        x = max(x+a[l],x*b[l]); //l-te miejsce robimy!
        x %= mod;

        //jestesmy w momencie gdzie mamy wiecej niz mod
        ll m = (mult_suf[l+1]*get_pot(mult_suf[r+1],mod-2))%mod;
        x = (x*m)%mod;
        //teraz dodajemy a
        ll v1 = (a_mult[l+1]-a_mult[r+1]+mod)%mod;
        x = (x + v1*get_pot(mult_suf[r+1],mod-2))%mod;

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

    return 0;
}

//g++ -O3 -static -Wall .cpp -std=c++17