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
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

int n;
const int N = 1 << 19;
const int MOD = 1000*1000*1000+7;
int A[N], B[N];
int nast[N], suma[N];
pair<int, int> T[2*N];

pair<int, int> mult(pair<int, int> x, pair<int, int> y) {
    return make_pair(((long long)x.first * (long long)y.first) % MOD, ((long long)x.second * (long long)y.first + (long long)y.second) % MOD);
}

pair<int, int> prod(int a, int b) {
    a += N; b += N;
    pair<int, int> r1 = T[a], r2 = make_pair(1, 0);
    while ((a >> 1) < (b >> 1)) {
        if (a % 2 == 0) r1 = mult(r1, T[a + 1]);
        if (b % 2 == 1) r2 = mult(T[b - 1], r2);
        a >>= 1;
        b >>= 1;
    }
    return mult(r1, r2);
}

int sum(int a, int b) {
    return (suma[b] + MOD - suma[a]) % MOD;
}

void przygotuj(){
    suma[0] = 0;
    for (int i = 0; i < n; ++i) {
        if (B[i] == 1){
            T[N + i] = make_pair(1, A[i]);
        } else {
            T[N + i] = make_pair(B[i], 0);
        }
        suma[i+1] = (suma[i] + A[i]) % MOD;
    }
    for (int i = N-1; i > 0; --i) T[i] = mult(T[2*i], T[2*i+1]);
    nast[n - 1] = n;
    for (int i = n - 2; i >= 0; --i) {
        if (B[i + 1] == 1)
            nast[i] = nast[i + 1];
        else
            nast[i] = i + 1;
    }
};

int query(int x, int l, int r){
    long long akum = (long long)x;
    while (l < r && akum < (long long)MOD) {
        if (B[l] == 1) {
            int h = min(r, nast[l]);
            akum += (long long)sum(l, h);
            l = h;
        } else {
            long long a1 = akum + (long long)A[l];
            long long a2 = akum * (long long)B[l];
            akum = max(a1, a2);
            l++;
        }
    }
    if (l < r) {
        pair<int, int> m = prod(l, r);
        akum = (akum % MOD) * (long long)m.first + (long long)m.second;
    }
    return akum % MOD;
}

int main(void){
    int q;
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; ++i) scanf("%d%d", A+i, B+i);
    przygotuj();
    for (int i = 0; i < q; ++i){
        int x, l, r;
        scanf("%d%d%d", &x, &l, &r); 
        int w = query(x, l, r);
        printf("%d\n", w);
    }
    return 0;
}