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

typedef long long ll;

#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define f(i, a, b) for (int i = a; i < b; i++)
#define rep(i, a) f(i, 0, a)
#define int ll
#define tv(a, x) for (auto& a : x)
#define DUZO 1000000000000000000LL
#define en "\n"
#define cn continue
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vii = vector<pii>;

const int MOD = 1'000'000'007;

vi a, b;
vi pref;
vi zyje; //ind gdzie realnie mozna mnozyc
vi dodatnie;

int pot(int a, int p) {
    if (p == 1) return a;
    if (p&1) return (a * pot(a, p - 1))%MOD;
    int p1 = pot(a, p/2);
    return (p1 * p1)%MOD;
}

void solve() {
    int n, q;
    cin >> n >> q;
    a.resize(n + 1);
    b.resize(n + 1);
    f(i, 1, n + 1) cin >> a[i] >> b[i];
    //pref trzyma sume po a
    pref.resize(n + 1);
    pref[0] = 0;
    f(i, 1, n+1) {
        pref[i] = a[i] + pref[i - 1];
    }
    f(i, 1, n + 1) {
        if (b[i] > 1) zyje.pb(i);
        if (a[i] > 0) dodatnie.pb(i);
    }
    vii suf(n + 2);
    suf[0] = {1, 0};
    f(i, 1, n + 1) {
        if (b[i] > 1) {
            suf[i] = {(suf[i - 1].st * b[i])%MOD, (suf[i - 1].nd * b[i])%MOD};
        } else {
            suf[i] = {suf[i - 1].st, (a[i] + suf[i - 1].nd)%MOD};
        }
    }
    rep(_, q) {
        int x, l, r;
        cin >> x >> l >> r;
        if (x == 0) {
            int wsk0 = lower_bound(all(dodatnie), l + 1) - dodatnie.begin();
            if (wsk0 == sz(dodatnie) || dodatnie[wsk0] > r) {
                cout << 0 << en;
                cn;
            }
            x = a[dodatnie[wsk0]];
            l = dodatnie[wsk0];
        }
        l++;
        int wsk = lower_bound(all(zyje), l) - zyje.begin();
        if (wsk == sz(zyje)) {
            cout << (x + pref[r] - pref[l - 1])%MOD << en;
            cn;
        }
        bool zr = false;
        int ind;
        f(j, 0, 30) {
            if (wsk == sz(zyje) || zyje[wsk] > r) {
                x += pref[r] - pref[l - 1];
                x %= MOD;
                cout << x << en;
                zr = true;
                break;
            }
            ind = zyje[wsk];
            x += pref[ind - 1] - pref[l - 1];
            if (x > MOD) {
                ind--;
                break;
            }
            x = max(x + a[ind], x * b[ind]);
            if (x > MOD) {
                break;
            }
            l = ind + 1;
            wsk++;
        }
        x %= MOD;
        if (zr) cn;
        ind++;
        int x1 = suf[r].st;
        int c1 = suf[r].nd;
        int x2 = suf[ind - 1].st;
        int c2 = suf[ind - 1].nd;
        int dzl = pot(x2, MOD - 2);
        int x3 = (x1 * dzl)%MOD;
        int c3 = (c1 - (c2 * x3))%MOD;
        if (c3 < 0) c3 += MOD;
        x = x * x3 + c3;
        x %= MOD;
        cout << x << en;
    }
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) {
        solve();
    }
    return 0;
}