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
#include <iostream>
#include <algorithm>
#include <vector>

constexpr size_t MAXN = 1e6;
constexpr size_t ADDN = 1<<20;
constexpr size_t TREE_SIZE = ADDN * 2 + 7;
constexpr int64_t MOD = 1e9 + 7;

size_t end_of_step[MAXN];
size_t next_non_zero_addition[MAXN];
int64_t val_add[TREE_SIZE];
int64_t val_mult[TREE_SIZE];
int64_t prefix_sum[MAXN];

int64_t tree_add[TREE_SIZE];
int64_t tree_mult[TREE_SIZE];

void build_tree() {
    for (size_t i = ADDN; i < TREE_SIZE; i++) {
        if (val_mult[i - ADDN] > 1) {
            tree_mult[i] = val_mult[i - ADDN];
            tree_add[i] = 0;
        } else {
            tree_add[i] = val_add[i - ADDN];
            tree_mult[i] = 1;
        }
    }
    for (int i = ADDN - 1; i >= 0; i--) {
        tree_add[i] = (tree_add[2 * i] * tree_mult[2 * i + 1] + tree_add[2 * i + 1]) % MOD;
        tree_mult[i] = (tree_mult[2 * i] * tree_mult[2 * i + 1]) % MOD;
    }
}

void build_prefix_sum(const size_t n) {
    for (size_t i = 0; i < n; i++) {
        prefix_sum[i + 1] = prefix_sum[i] + val_add[i];
    }
}

void build_next_non_zero_addition(const int64_t n) {
    next_non_zero_addition[n] = n;
    for (int i = n - 1; i >= 0; i--) {
        if (val_add[i] == 0) {
            next_non_zero_addition[i] = next_non_zero_addition[i + 1];
        } else {
            next_non_zero_addition[i] = i;
        }
    }
}

void build_end_of_step(const int64_t n) {
    end_of_step[n] = n;
    for (int i = n - 1; i >= 0; i--) {
        if (val_mult[i] > 1) {
            end_of_step[i] = i;
        } else {
            end_of_step[i] = end_of_step[i + 1];
        }
    }
}


int64_t make_step(int64_t val, size_t l, size_t r, const bool is_big) {
    if (l >= r) {
        return val % MOD;
    }
    if (is_big == false) {
        if (val >= MOD) {
            return make_step(val % MOD, l, r, true);
        }
        if (val == 0) {
            return make_step(val, next_non_zero_addition[l], r, false);
        }
        if (val_mult[l] > 1) {
            return make_step(std::max(val + val_add[l], val * val_mult[l]), l+1, r, false);
        }
        if (end_of_step[l] >= r) {
            return (val + prefix_sum[r] - prefix_sum[l]) % MOD; 
        } else {
            return make_step(val + prefix_sum[end_of_step[l]] - prefix_sum[l], end_of_step[l], r, false);
        }
    } else {
        l += ADDN;
        r += ADDN;
        val = (val * tree_mult[l] + tree_add[l]) % MOD; 
        std::vector<std::pair<int64_t, int64_t>> right_ops;
        //right_ops.emplace_back(tree_mult[r], tree_add[r]);
        
        int64_t total_mult = 1;
        int64_t total_add = 0;
        while (l / 2 < r / 2) {
            if (l % 2 == 0) {
                val = (val * tree_mult[l + 1] + tree_add[l + 1]) % MOD;
            }
            if (r % 2 == 1) {
                right_ops.emplace_back(tree_mult[r - 1], tree_add[r - 1]);
            }
            l /= 2;
            r /= 2;
        }
        std::reverse(right_ops.begin(), right_ops.end());
        for (const auto [mlt, ad] : right_ops) {
            val = (val * mlt + ad) % MOD;
        }
        return val;
    }
}

int main() {
    size_t n, q;
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> n >> q;
    for (size_t i = 0; i < n; i++) {
        std::cin >> val_add[i] >> val_mult[i];
    }
    build_tree();
    build_prefix_sum(n);
    build_end_of_step(n);
    build_next_non_zero_addition(n);
    for (size_t i = 0; i < q; i++) {
        int64_t x, l, r;
        std::cin >> x >> l >> r;
        std::cout << make_step(x, l, r, false) << '\n';
    }
    return 0;
}