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>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define int long long
#define ld long double
#define pb push_back

using namespace std;
#define rg ranges

constexpr int mod = 1e9 + 7;

int tB;
vector<int> t, lz;

void push(int v) {
    auto l = lz[v];
    lz[v] = 1;
    rep(s, 2 * v, 2 * v + 2) {
        t[s] *= l;
        t[s] %= mod;
        lz[s] *= l;
        lz[s] %= mod;
    }
}

void tSet(int i, int x, int mL = 0, int mR = tB - 1, int v = 1) {
    DEBUG if(v == 1) DC << "tSet(" << i << ' ' << x << ")\n";
    if(mL == mR) t[v] = x, lz[v] = 1;
    else {
        push(v);
        auto m = (mL + mR) / 2;
        if(i <= m) tSet(i, x, mL, m, v * 2);
        else tSet(i, x, m + 1, mR, v * 2 + 1);
        t[v] = (t[2 * v] + t[2 * v + 1]) % mod;
    }
}

void tMul(int l, int r, int x, int mL = 0, int mR = tB - 1, int v = 1) {
    DEBUG if(v == 1) DC << "tMul(" << l << ' ' << r << ' ' << x << ")\n";
    if(l > mR || r < mL) return;
    if(l <= mL && mR <= r) {
        t[v] = t[v] * x % mod;
        lz[v] = lz[v] * x % mod;
        return;
    }
    push(v);
    tMul(l, r, x, mL, (mL + mR) / 2, v * 2);
    tMul(l, r, x, (mL + mR) / 2 + 1, mR, v * 2 + 1);
    t[v] = (t[2 * v] + t[2 * v + 1]) % mod;
}

int tSum(int l, int r, int mL = 0, int mR = tB - 1, int v = 1) {
    if(l > mR || r < mL) return 0;
    if(l <= mL && mR <= r) return t[v];
    push(v);
    return (tSum(l, r, mL, (mL + mR) / 2, v * 2) + tSum(l, r, (mL + mR) / 2 + 1, mR, v * 2 + 1)) % mod;
}

int fastPow(int a, int x) {
    if(!x) return 1;
    auto h = fastPow(a, x / 2);
    h = h * h % mod;
    if(x & 1) h = h * a % mod;
    return h;
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<array<int, 2>> v(n);
    rep(i, 0, n) rep(j, 0, 2) cin >> v[i][j];
    vector<array<int, 3>> qs(q), qs2;
    qs2.reserve(q);
    vector<int> answers(q);
    rep(i, 0, q) rep(j, 0, 3) cin >> qs[i][j];
    vector<int> nextMul(n + 1, n), addSum(n + 1), mulProd(n + 1, 1);
    repD(i, n - 1, -1) nextMul[i] = (v[i][1] == 1 ? nextMul[i + 1] : i);
    rep(i, 0, n) addSum[i + 1] = addSum[i] + v[i][0], mulProd[i + 1] = mulProd[i] * v[i][1] % mod;
    rep(i, 0, q) {
        auto [x, l, r] = qs[i];
        r--;
        auto it = l;
        while(it <= r && x < mod) {
            auto nit = nextMul[it];
            nit = min(nit, r + 1);
            if(nit == it) {
                x = max(x + v[nit][0], x * v[nit][1]);
                it++;
                continue;
            }
            auto add = addSum[nit] - addSum[it];
            x += add;
            it = nit;
        }
        if(it > r) {
            answers[i] = x % mod;
            continue;
        }
        answers[i] = x % mod * mulProd[r + 1] % mod * fastPow(mulProd[it], mod - 2) % mod;
        qs2.pb({r, it, i});
    }
    rg::sort(qs2);
    tB = 1 << (32 - __builtin_clz(max(1, (int32_t)n - 1)));
    t.resize(2 * tB);
    lz.resize(2 * tB, 1);
    int it = -1;
    rep(i, 0, (int) qs2.size()) {
        auto [r, l, qi] = qs2[i];
        while(it < r) {
            it++;
            auto [x, y] = v[it];
            if(y == 1) tSet(it, x);
            else tMul(0, it, y);
        }
        answers[qi] = (answers[qi] + tSum(l, r)) % mod;
    }
    repIn(i, answers) cout << i << '\n';
}