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.util.*;
/*
2 72
77 5
91 6
5
1 26 1
1 51 8
1 6 9
3
3
 */
public class Ed1333 {
	static long p = (long)(1e7 + 19);
	static long q = (long)(1e9 + 7);
	static int oo = 987654321;
	public static void main(String[] args) {
		
		Scanner qwe = new Scanner(System.in);
		
		int n = qwe.nextInt();
		int k  =qwe.nextInt();
		
		ArrayList<item> items = new ArrayList<item>();
		
		
		for(int i =0; i < n; i++){
			items.add(new item(qwe.nextInt(),qwe.nextInt(),0,oo));
		}
		
		int q = qwe.nextInt();
		
		//ArrayList<Integer> qpoints = new ArrayList<Integer>();
		TreeSet<query> ts = new TreeSet<query>();
		int qdex = 0;
		for(int i =1; i <= q; i++){
			
			int type =  qwe.nextInt();
			if(type == 1){
				items.add(new item(qwe.nextInt(),qwe.nextInt(),i,oo));
			}
			else if(type == 2){
				int x = qwe.nextInt()-1;
				items.get(x).end = i;
			}
			else{
				ts.add(new query(i,qdex++));
			}
		}
		IntervalTree segTree = new IntervalTree(ts.size(), k);
		
		for(item i : items){
			
			query l = ts.ceiling(new query(i.start,-1));
			query r = ts.floor(new query(i.end,-1));
			
			if(l != null && r != null && l.compindex <= r.compindex){
				i.l = l.compindex;
				i.h = r.compindex;
				
				//System.out.println("l: " + i.l  +" r: " + i.h + " v: " + i.v  + " w: " + i.w);
				
				segTree.root.increment(i.l, i.h, i);
			}
			//else System.out.println("l: " + l + " r: " + r);

			
		}
		
		for(query que : ts){
			System.out.println(segTree.root.query(que.compindex));
		}
		
		
		qwe.close();
	}
	
	
	static class IntervalTree {
		 val root;
		 int maxw;
		public IntervalTree(int n, int maxw){
			this.maxw = maxw;
			root = new val(0,n-1);
			root.knap = new int[maxw+1];
		}
		 class val{
			val left,right;
			ArrayList<item> carry;
			int lo, hi;
			int[] knap;
			boolean haspushed;
			public val(int l, int h){
				lo = l;
				hi = h;
	
				carry = new ArrayList<item>();
				haspushed = false;
				if(lo != hi){
					int m = (lo+hi) / 2;
					left = new val(lo,m);
					right = new val(m+1,hi);
				}
				else {

				}
				
			}
			
			public void incorp(item put){
				for(int i =knap.length-1; i-put.w >= 0; i--){
					knap[i] = Math.max(knap[i], knap[i-put.w] + put.v);
				}
			}
			
			//increment [l,h] by x
			public void increment(int l,int h, item put){
				if(h < lo || l > hi)return;
				if(lo >= l && hi <= h){
					incorp(put);
				}
				else{
					carry.add(put);
				}
				haspushed = false;
			}
			//all original increment calls first
			public long query(int x){
				if(left == null){
					long ret = 0;
					long mult = 1;
					
					//System.out.println("x: " + x  + " " + Arrays.toString(knap));
					
					for(int i =1; i < knap.length; i++){
						ret += knap[i]*mult;
						ret %= q;
						
						mult *= p;
						mult %= q;
					}
					
					knap = null;
					
					return ret;
				}
				
				//System.out.println("l: " + lo  + " hi: " + hi + " " + Arrays.toString(knap));
				
				if(carry.size() != 0 || !haspushed){
					 
					left.knap = Arrays.copyOf(knap, knap.length);
					right.knap = Arrays.copyOf(knap, knap.length);
					
					for(item it : carry){
						left.increment(it.l, it.h, it);
						right.increment(it.l, it.h, it);
					}
					
					carry.clear();
					haspushed = true;
					knap = null;
				}
				
				if(x <= left.hi) return left.query(x);
				else return right.query(x);
				
			}
			
		}

	}

	
	static class query implements Comparable<query>{
		int index, compindex;
		
		public query(int i, int ci){
			index = i;
			compindex = ci;
		}
		
		@Override
		public int compareTo(query o) {
			return index - o.index;
		}

		@Override
		public String toString() {
			return " [index=" + index + ", compindex=" + compindex + "]";
		}
		
		
		
	}
	
	static class item{
		int v;
		int w;
		int start, end;
		int l,h;
		public item(int v, int w, int start, int end){
			this.v = v;
			this.w =w;
			this.start = start;
			this.end = end;
		}
		
	}

}