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
#pragma GCC optimize("O3,unroll-loops,inline")
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;

const ll mod = 1e9+7;

struct Int {
    ll val;
    bool islarge = 0;
    Int(ll i) {
        val = i % mod;
        islarge = i >= mod;
    }
    Int(ll v, bool g) : val(v), islarge(g) {}
    Int operator * (Int b) {
        ll retval = val * b.val;
        bool retisbig = islarge or b.islarge or retval >= mod;
        return {retval % mod, retisbig};
    }
    Int operator + (Int b) {
        ll retval = val + b.val;
        bool retisbig = islarge or b.islarge or retval >= mod;
        return {retval % mod, retisbig};
    }
};

struct event{
    Int a = 0, b = 1;

    event operator*(event& o) {
        return {a*o.b + o.a, b*o.b};
    }
};

template<class T>
struct ST{
    T unite(T l, T r){
        return l * r; // or any associative operation
    }

    int n, mxd;
    vector<vector<T>> suf, pref;

    ST(vector<T> a) : n(sz(a)), mxd(__lg(n)+1), suf(mxd,vector<T>(n)), pref(mxd,vector<T>(n)){
        for (int i=0,w=1; i<mxd; ++i, w*=2)
            for (int b = 0; b < n; b += w){
                int lim = min(b+w,n)-1;
                T cur = a[b];
                for(int k = b; k<lim; cur = unite(cur,a[++k]))
                    pref[i][k] = cur;
                pref[i][lim] = cur;

                cur = a[lim];
                for (int k = lim; k>b; cur = unite(a[--k],cur))
                    suf[i][k] = cur;
                suf[i][b] = cur;
        }
    }

    // halfopen segment [l,r)
    T get(int l, int r){
        if (l >= r) return {0, 1};
        if (l==--r) return suf[0][l];
        int d = __lg(l^r);
        return unite(suf[d][l],pref[d][r]);
    }
};


int main(){
    cin.tie(NULL),ios::sync_with_stdio(false);
    
    int n,q; cin >> n >> q;
    vector<event> a(n), greedy(n);
    for(auto& e : a){
        int x,y; cin >> x >> y;
        e.a = x, e.b = y;
    }

    
    rep(i,0,n){
        if (a[i].b.val == 1) greedy[i] = {a[i].a, 1};
        else greedy[i] = {0, a[i].b};
    }

    ST st(greedy);
    
    vi nxtchoice(n+1,n);
    for(int i = n-1; i >= 0; --i){
        if (a[i].a.val > 0 and a[i].b.val > 1) nxtchoice[i] = i;
        else nxtchoice[i] = nxtchoice[i+1];
    }

    while(q--) {
        int x,l,r; cin >> x >> l >> r;
        Int val(x);
        while(l < r and !val.islarge) {
            int to = min(r,nxtchoice[l]);
            event trans = st.get(l, to);
            val = trans.a + trans.b * val;
            if (val.islarge){
                l = to;
                break;
            }else if (to < r){
                ll sum = val.val + a[to].a.val;
                ll prod = val.val * a[to].b.val;
                val = max(sum, prod);
                l = to + 1;
            }else l = to;
        }
        event trans = st.get(l,r);
        val = trans.a + trans.b * val;
        cout << val.val << '\n';
    }
}