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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.stream.IntStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Reader;
import java.io.InputStreamReader;
import java.util.Objects;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Ruins He
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    TaskE solver = new TaskE();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskE {
    private static final long Q = (long) (1e7 + 19);
    private static final long P = (long) (1e9 + 7);
    private int n;
    private int m;
    private int[] v;
    private int[] w;
    private int[][] queries;
    Pair<Integer, Integer>[] items;
    private int[] queryConut;
    private int itemsCount;
    private int[] start;
    private int[] end;
    private long[][] dp;
    private OutputWriter out;

    @SuppressWarnings("unchecked")
    public void solve(int testNumber, InputReader in, OutputWriter out) {
      this.out = out;
      n = in.nextInt();
      m = in.nextInt();
      v = new int[n];
      w = new int[n];
      for (int i = 0; i < n; i++) {
        v[i] = in.nextInt();
        w[i] = in.nextInt();
      }
      int q = in.nextInt();
      queries = new int[q][];
      itemsCount = n;
      int time = 1;
      for (int i = 0; i < q; i++) {
        int type = in.nextInt();
        if (type == 1) {
          queries[i] = new int[2];
          queries[i][1] = in.nextInt();
          queries[i][0] = in.nextInt();
          itemsCount++;
        } else if (type == 2) {
          queries[i] = new int[1];
          queries[i][0] = in.nextInt() - 1;
        } else {
          queries[i] = new int[0];
        }
        if (type != 3) time++;
      }
      time++;
      items = new Pair[itemsCount];
      start = new int[itemsCount];
      end = new int[itemsCount];
      queryConut = new int[time + 1];
      Arrays.fill(end, -1);
      for (int i = 0; i < n; i++) items[i] = Pair.of(w[i], v[i]);
      time = 1;
      int currentItemId = n;
      for (int i = 0; i < q; i++) {
        if (queries[i].length == 2) {
          time++;
          items[currentItemId] = Pair.of(queries[i][0], queries[i][1]);
          start[currentItemId] = time;
          currentItemId++;
        } else if (queries[i].length == 1) {
          end[queries[i][0]] = time;
          time++;
        } else {
          queryConut[time]++;
        }
      }
      time++;
      for (int i = 0; i < itemsCount; i++) {
        if (end[i] == -1) end[i] = time;
      }
      for (int i = 1; i <= time; i++) queryConut[i] += queryConut[i - 1];
      int maxDepth = calculateDepth(0, time);
      dp = new long[maxDepth + 1][m + 1];
      dfs(1, 0, time, IntStream.range(0, itemsCount).toArray());
    }

    private int calculateDepth(int l, int r) {
      int count = l == 0 ? queryConut[r] : (queryConut[r] - queryConut[l - 1]);
      if (count == 0) return 0;
      else if (l == r) return 1;
      else {
        int mid = (l + r) >> 1;
        return Math.max(calculateDepth(l, mid), calculateDepth(mid + 1, r)) + 1;
      }
    }

    private void dfs(int depth, int l, int r, int[] itemIds) {
      int count = l == 0 ? queryConut[r] : (queryConut[r] - queryConut[l - 1]);
      if (count == 0) return;
      System.arraycopy(dp[depth - 1], 0, dp[depth], 0, m + 1);
      for (int itemId : itemIds) {
        if (start[itemId] <= l && r <= end[itemId]) {
          for (int i = m; i >= items[itemId].first; i--)
            dp[depth][i] = Math.max(
                dp[depth][i], dp[depth][i - items[itemId].first] + items[itemId].second);
        }
      }
      if (l == r) {
        long res = 0;
        for (int i = m; i >= 1; i--) res = (res * Q + dp[depth][i]) % P;
        for (int i = 0; i < count; i++) out.println(res);
        return;
      }
      int mid = (l + r) >> 1;
      int leftCount = 0, rightCount = 0;
      for (int itemId : itemIds) {
        if (start[itemId] > l || end[itemId] < r) {
          if (start[itemId] <= mid) leftCount++;
          if (end[itemId] > mid) rightCount++;
        }
      }
      int[] left = new int[leftCount];
      int[] right = new int[rightCount];
      for (int itemId : itemIds) {
        if (start[itemId] > l || end[itemId] < r) {
          if (start[itemId] <= mid) left[--leftCount] = itemId;
          if (end[itemId] > mid) right[--rightCount] = itemId;
        }
      }
      dfs(depth + 1, l, mid, left);
      dfs(depth + 1, mid + 1, r, right);
    }

  }

  static class Pair<F extends Comparable<F>, S extends Comparable<S>> implements Comparable<Pair<F, S>> {
    public F first;
    public S second;

    public Pair(F first, S second) {
      this.first = first;
      this.second = second;
    }

    public static <F extends Comparable<F>, S extends Comparable<S>> Pair<F, S> of(
        F first, S second) {
      return new Pair<>(first, second);
    }


    public int compareTo(Pair<F, S> other) {
      int fd = this.first.compareTo(other.first);
      if (fd != 0) return fd;
      else return this.second.compareTo(other.second);
    }


    public String toString() {
      return "Pair{" + first + ", " + second + "}";
    }


    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;

      Pair<?, ?> pair = (Pair<?, ?>) o;

      if (first != null ? !first.equals(pair.first) : pair.first != null) return false;
      return !(second != null ? !second.equals(pair.second) : pair.second != null);

    }


    public int hashCode() {
      return Objects.hash(first, second);
    }

  }

  static class InputReader {
    public final BufferedReader reader;
    public StringTokenizer tokenizer = null;

    public InputReader(Reader reader) {
      this.reader = new BufferedReader(reader, 32767);
    }

    public InputReader(InputStream inputStream) {
      this(new InputStreamReader(inputStream));
    }

    public String next() {
      if (hasNext()) return tokenizer.nextToken();
      else throw new NoSuchElementException();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public boolean hasNext() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          String nextLine = reader.readLine();
          if (nextLine == null) return false;
          tokenizer = new StringTokenizer(nextLine);
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.hasMoreTokens();
    }

  }

  static class OutputWriter {
    private final PrintWriter writer;

    private OutputWriter(Writer writer, boolean autoFlush) {
      this.writer = new PrintWriter(new BufferedWriter(writer, 32767), autoFlush);
    }

    public OutputWriter(Writer writer) {
      this(writer, true);
    }

    public OutputWriter(OutputStream outputStream) {
      this(new OutputStreamWriter(outputStream), false);
    }

    public OutputWriter println(long value) {
      writer.println(value);
      return this;
    }

    public void close() {
      writer.close();
    }

  }
}