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

using namespace std;

typedef long long LL;

// #define dprint(...) printf(__VA_ARGS__)
#define dprint(...)

const int M = 1000000007;
int n, SIZE;

vector<int> a, b;

vector<int> non1;

struct E {
  LL a, b;
  bool am, bm;

  E() : E(0, 1) {}
  E(LL aa, LL bb): a(aa), b(bb), am(false), bm(false) {}
};

vector<E> A;
vector<E> opt;


E aggr(E left, E right) {
  E res;
  res.a = left.a * right.b + right.a;
  res.am = left.am || (left.a > 0 && right.bm) || right.am;
  res.b = left.b * right.b;
  res.bm = left.bm || right.bm;
  if (res.a >= M) { res.am = true; res.a = res.a % M; }
  if (res.b >= M) { res.bm = true; res.b = res.b % M; }
  return res;
}

E query(int p, int c, int d, int C, int D) {
  dprint("Szukam %d %d %d %d %d\n", p, c, d, C, D);

  if (d <= C) return E();
  if (D <= c) return E();
  if (c <= C && D <= d) {
    dprint("Zwracam %d: %lld %lld %d %d\n", p, opt[p].a, opt[p].b, opt[p].am, opt[p].bm);
    return opt[p];
  }

  return aggr(query(p*2, c, d, C, (C+D)/2), query(p*2+1, c, d, (C+D)/2, D));
}

E query(int c, int d) {
  return query(1, c, d, 0, SIZE);
}

int main() {
  int q; scanf(" %d %d", &n, &q);

  a.resize(n); b.resize(n);
  for (int i=0; i<n; ++i) {
    scanf(" %d %d", &a[i], &b[i]);
  }

  non1.resize(n+1); non1[n] = n;
  for (int i=n-1; i>=0; --i) {
    if (b[i] == 1) {
      non1[i] = non1[i+1];
    } else {
      non1[i] = i;
    }
  }

  SIZE = 1; while (SIZE <= n) SIZE *= 2;

  opt.resize(SIZE*2);
  for (int i=0; i<n; ++i) {
    if (b[i] == 1) {
      opt[SIZE+i] = E(a[i], 1);
    } else {
      opt[SIZE+i] = E(0, b[i]);
    }
  }
  for (int i=SIZE-1; i>0; --i) {
    opt[i] = aggr(opt[i*2], opt[i*2+1]);
  }

  for (int i=0; i<SIZE*2; ++i) {
    dprint("%d: %lld %lld %d %d\n", i, opt[i].a, opt[i].b, opt[i].am, opt[i].am);
  }

  for (int i=0; i<q; ++i) {
    LL x;
    bool m = false;
    int l, r; scanf(" %lld %d %d", &x, &l, &r);

    while (l < r) {
      if (m) {
        dprint("Skacze do konca: %lld - %d -> %d\n", x, l, r);
        E e = query(l, r);
        dprint("%lld %lld\n", e.a, e.b);
        x = (x * e.b + e.a) % M;
        l = r+1;
      } else if (b[l] == 1) {
        int t = min(non1[l], r);
        dprint("Skacze tylko plusy: %lld - %d -> %d\n", x, l, t);
        E e = query(l, t);
        x = x * e.b + e.a;
        if (x >= M) { m = true; x %= M; }
        l = t;
      } else {
        dprint("Kroczek: %lld - %d, %d\n", x, a[l], b[l]);
        x = max(x + a[l], x * b[l]);
        if (x >= M) { m = true; x %= M; }
        ++l;
      }
    }

    printf("%lld\n", x);
  }
  return 0;
}