Problem: There's a famous museum in the city where Kleofáš lives. In the museum, n exhibits (numbered 1 through n) had been displayed for a long time; the i-th of those exhibits has value vi and mass wi. 

Then, the museum was bought by a large financial group and started to vary the exhibits. At about the same time, Kleofáš... gained interest in the museum, so to say.

You should process q events of three types:

  * type 1 — the museum displays an exhibit with value v and mass w; the exhibit displayed in the i-th event of this type is numbered n + i (see sample explanation for more details)
  * type 2 — the museum removes the exhibit with number x and stores it safely in its vault
  * type 3 — Kleofáš visits the museum and wonders (for no important reason at all, of course): if there was a robbery and exhibits with total mass at most m were stolen, what would their maximum possible total value be?



For each event of type 3, let s(m) be the maximum possible total value of stolen exhibits with total mass  ≤ m.

Formally, let D be the set of numbers of all exhibits that are currently displayed (so initially D = {1, ..., n}). Let P(D) be the set of all subsets of D and let 

<image>

Then, s(m) is defined as 

<image>

Compute s(m) for each <image>. Note that the output follows a special format.

Input

The first line of the input contains two space-separated integers n and k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 1000) — the initial number of exhibits in the museum and the maximum interesting mass of stolen exhibits. 

Then, n lines follow. The i-th of them contains two space-separated positive integers vi and wi (1 ≤ vi ≤ 1 000 000, 1 ≤ wi ≤ 1000) — the value and mass of the i-th exhibit.

The next line contains a single integer q (1 ≤ q ≤ 30 000) — the number of events.

Each of the next q lines contains the description of one event in the following format:

  * 1 v w — an event of type 1, a new exhibit with value v and mass w has been added (1 ≤ v ≤ 1 000 000, 1 ≤ w ≤ 1000)
  * 2 x — an event of type 2, the exhibit with number x has been removed; it's guaranteed that the removed exhibit had been displayed at that time
  * 3 — an event of type 3, Kleofáš visits the museum and asks his question



There will be at most 10 000 events of type 1 and at least one event of type 3.

Output

As the number of values s(m) can get large, output the answers to events of type 3 in a special format.

For each event of type 3, consider the values s(m) computed for the question that Kleofáš asked in this event; print one line containing a single number 

<image>

where p = 107 + 19 and q = 109 + 7.

Print the answers to events of type 3 in the order in which they appear in the input.

Examples

Input

3 10
30 4
60 6
5 1
9
3
1 42 5
1 20 3
3
2 2
2 4
3
1 40 6
3


Output

556674384
168191145
947033915
181541912


Input

3 1000
100 42
100 47
400 15
4
2 2
2 1
2 3
3


Output

0

Note

In the first sample, the numbers of displayed exhibits and values s(1), ..., s(10) for individual events of type 3 are, in order: 

<image> <image> <image> <image>

The values of individual exhibits are v1 = 30, v2 = 60, v3 = 5, v4 = 42, v5 = 20, v6 = 40 and their masses are w1 = 4, w2 = 6, w3 = 1, w4 = 5, w5 = 3, w6 = 6.

In the second sample, the only question is asked after removing all exhibits, so s(m) = 0 for any m.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma warning(disable : 4996)
using namespace std;
const long long P = 10000019;
const long long Q = 1000000007;
long long Pm[1011];
int n, k;
int vv[15011], ww[15011];
int ss[15011], ee[15011];
int tt[30011], tw[30011];
class ROW {
 public:
  int val[1001];
};
ROW addRow(ROW& a, int v, int w) {
  ROW r = a;
  for (long long i = k; i >= w; i--) {
    r.val[i] = max(r.val[i], r.val[i - w] + v);
  }
  return r;
}
ROW rr[30011], rg[30011], emptyRow;
bool frg[30011];
map<int, int> num_map;
vector<int> t3;
int main() {
  scanf("%d %d", &n, &k);
  int in = n;
  int t = 0;
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &vv[i], &ww[i]);
    ss[i] = t++;
    ee[i] = -1;
    num_map[i + 1] = i;
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int type, x;
    scanf("%d", &type);
    switch (type) {
      case 1:
        scanf("%d %d", &vv[n], &ww[n]);
        ss[n] = t++;
        ee[n] = -1;
        num_map[n + 1] = n;
        n++;
        break;
      case 2:
        scanf("%d", &x);
        x = num_map[x];
        ee[x] = t++;
        break;
      case 3:
        t3.push_back(t);
        break;
    }
  }
  for (int i = 0; i < n; i++) {
    if (ee[i] == -1) ee[i] = t++;
    tt[ss[i]] = 1;
    tw[ss[i]] = i;
    tt[ee[i]] = 2;
    tw[ee[i]] = i;
  }
  vector<int> tab;
  for (int i = 0; i + 1 < t; i++) {
    if (tt[i] == 2 && tt[i + 1] == 1) {
      tab.push_back(i);
    }
  }
  if (tab.size() > 0) {
    int last = (int)tab.size() - 1;
    int fs = tab[0];
    int fe = tab[last] + 1;
    for (int i = 0; i < n; i++) {
      if (ss[i] <= fs && fe <= ee[i]) {
        rr[0] = addRow(rr[0], vv[i], ww[i]);
      }
    }
    vector<int> rs, re;
    rs.push_back(0);
    re.push_back((int)tab.size() - 1);
    for (int i = 0; i < (int)rs.size(); i++) {
      int s = rs[i], e = re[i];
      if (s == e) {
        rg[tab[s]] = rr[i];
        frg[tab[s]] = true;
        continue;
      }
      int x = rs.size();
      int m = (s + e) / 2;
      rr[x] = rr[i];
      rr[x + 1] = rr[i];
      for (int p = tab[m] + 1; p <= tab[e]; p++) {
        int w = tw[p];
        if (tt[p] == 2 && ss[w] <= tab[s]) {
          rr[x] = addRow(rr[x], vv[w], ww[w]);
        }
      }
      for (int p = tab[s] + 1; p <= tab[m + 1]; p++) {
        int w = tw[p];
        if (tt[p] == 1 && ee[w] >= tab[e] + 1) {
          rr[x + 1] = addRow(rr[x + 1], vv[w], ww[w]);
        }
      }
      rs.push_back(s);
      re.push_back(m);
      rs.push_back(m + 1);
      re.push_back(e);
    }
  }
  vector<pair<ROW*, int> > bfs;
  bfs.push_back(make_pair(&emptyRow, -1));
  bfs.push_back(make_pair(&emptyRow, t - 1));
  for (int i = 0; i < t; i++) {
    if (frg[i]) {
      bfs.push_back(make_pair(&rg[i], i));
    }
  }
  for (int i = 0; i < (int)bfs.size(); i++) {
    ROW* row = bfs[i].first;
    int p = bfs[i].second;
    if (p > 0 && tt[p] == 2 && !frg[p - 1]) {
      int w = tw[p];
      frg[p - 1] = true;
      rg[p - 1] = addRow(*row, vv[w], ww[w]);
      bfs.push_back(make_pair(&rg[p - 1], p - 1));
    }
    if (p + 1 < t && tt[p + 1] == 1 && !frg[p + 1]) {
      int w = tw[p + 1];
      frg[p + 1] = true;
      rg[p + 1] = addRow(*row, vv[w], ww[w]);
      bfs.push_back(make_pair(&rg[p + 1], p + 1));
    }
  }
  Pm[0] = 1;
  for (int m = 1; m <= k; m++) {
    Pm[m] = (Pm[m - 1] * P) % Q;
  }
  for (int i = 0; i < (int)t3.size(); i++) {
    int t = t3[i] - 1;
    long long res = 0;
    for (int m = 1; m <= k; m++) {
      res = (res + rg[t].val[m] * Pm[m - 1]) % Q;
    }
    printf("%I64d\n", res);
  }
  return 0;
}