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
130
131
132
133
134
135
136
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <numeric>

#define LL long long

const LL modulo = 1'000'000'007;
const int mxn = 5e5 + 10;

int n, q;
LL sum_left[mxn];
LL mul_right[mxn];


LL pref_sum[mxn]; // it is not modulo (we need to know when it crosses modulo)
int next_non_1[mxn];
LL mul_pref_part[mxn];
LL sum_pref_part[mxn];

LL fast_pow(LL base, LL exp) {
    LL result = 1;
    base %= modulo;
    while (exp > 0) {
        if (exp & 1LL) {
            result = (result * base) % modulo;
        }
        base = (base * base) % modulo;
        exp /= 2;
    }
    return result;
}

LL inverse_modulo(LL a) {
    return fast_pow(a, modulo - 2LL);
}

// calculate optimal additions/multiplications when the value is already
// over modulo
std::pair<LL, LL> range_value_optimal(int l, int r) {
    LL mul_result = (mul_pref_part[r] * inverse_modulo(mul_pref_part[l - 1])) % modulo;
    LL sum_result = (sum_pref_part[r] + modulo - (mul_result * sum_pref_part[l - 1] % modulo)) % modulo;
    return {sum_result, mul_result};
}

// jump the range filled with 1s on multiplications side
// returns sum that was jumped over
std::pair<LL, int> sum_jump(int l, int r) {
    // jump to next non 1 or to the finish of the range
    int nxt = std::min(next_non_1[l], r + 1);
    int end_idx = nxt - 1; 
    
    // Poprawna suma od 'l' do 'end_idx' włącznie
    LL sum = pref_sum[end_idx] - pref_sum[l - 1];
    return {sum, end_idx};
}

LL answer_query(LL x, int l, int r) {
    
    bool more_than_modulo = false;

    for (int i = l + 1; i <= r; i++) {
        if (!more_than_modulo) {
            // less than modulo, choose the best absolute
            if (mul_right[i] == 1) {
                // you can jump over 1s
                auto p = sum_jump(i, r);
                x += p.first;
                i = p.second;
            } else {
                x = std::max(x + sum_left[i], x * mul_right[i]);
            }
            if (x >= modulo) {
                more_than_modulo = true;
            }
        } else {
            // more than modulo, add whole range till the end and exit
            auto p = range_value_optimal(i, r);
            LL sum_result = p.first;
            LL mul_result = p.second;
            x = (((x * mul_result) % modulo) + sum_result) % modulo;
            break;
        }
        x %= modulo;
    }
    return x;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n >> q;
    // 1x + 0
    mul_pref_part[0] = 1; 
    sum_pref_part[0] = 0;
    for (int i = 1; i <= n; i++) {
        std::cin >> sum_left[i] >> mul_right[i];
        pref_sum[i] = pref_sum[i - 1] + sum_left[i];
        // calculate ranges when doing optimal strategy over modulo
        if (mul_right[i] == 1LL) {
            // sum
            sum_pref_part[i] = (sum_pref_part[i - 1] + sum_left[i]) % modulo;
            mul_pref_part[i] = mul_pref_part[i - 1];
        } else {
            // multiplication
            sum_pref_part[i] = (sum_pref_part[i - 1] * mul_right[i]) % modulo;
            mul_pref_part[i] = (mul_pref_part[i - 1] * mul_right[i]) % modulo;
        }
    }
    // calculate next non-1 mul (to do jumps when in prefix mode) 
    next_non_1[n + 1] = n + 1;
    for (int i = n; i >= 1; i--) {
        if (mul_right[i] != 1) {
            next_non_1[i] = i;
        } else {
            next_non_1[i] = next_non_1[i + 1];
        }
    }

    while (q--) {
        LL x;
        int l, r;
        std::cin >> x >> l >> r;
        std::cout << answer_query(x, l, r) << "\n";
    }

    return 0;
}