Problem: Lena is a programmer. She got a task to solve at work.

There is an empty set of pairs of integers and n queries to process. Each query is one of three types:

  1. Add a pair (a, b) to the set. 
  2. Remove a pair added in the query number i. All queries are numbered with integers from 1 to n. 
  3. For a given integer q find the maximal value x·q + y over all pairs (x, y) from the set. 



Help Lena to process the queries.

Input

The first line of input contains integer n (1 ≤ n ≤ 3·105) — the number of queries.

Each of the next n lines starts with integer t (1 ≤ t ≤ 3) — the type of the query.

A pair of integers a and b ( - 109 ≤ a, b ≤ 109) follows in the query of the first type.

An integer i (1 ≤ i ≤ n) follows in the query of the second type. It is guaranteed that i is less than the number of the query, the query number i has the first type and the pair from the i-th query is not already removed.

An integer q ( - 109 ≤ q ≤ 109) follows in the query of the third type.

Output

For the queries of the third type print on a separate line the desired maximal value of x·q + y.

If there are no pairs in the set print "EMPTY SET".

Example

Input

7
3 1
1 2 3
3 1
1 -1 100
3 1
2 4
3 1


Output

EMPTY SET
5
99
5

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class CF_678F2 {

	static long NULL = -2_000_000_000_000_000_000L;
	static long e18plus5 = 3_000_000_000_000_000_005L;
	public static void main(String[] args) {
		FS in = new FS();
		PrintWriter out = new PrintWriter(System.out);
		int N = in.nextInt();
		
		Segtree st = new Segtree(N);
		int rr[] = new int[N];
		Arrays.fill(rr, N-1);
		
		int inp[][] = new int[N][];
		for(int i = 0; i < N; i++) {
			int t = in.nextInt();
			if(t == 1) {
				inp[i] = new int[3];
				inp[i][0] = t;
				inp[i][1] = in.nextInt();
				inp[i][2] = in.nextInt();
			}
			else if(t == 2) {
				inp[i] = new int[2];
				inp[i][0] = t;
				inp[i][1] = in.nextInt()-1;
				rr[inp[i][1]] = i;
			}
			else {
				inp[i] = new int[2];
				inp[i][0] = t;
				inp[i][1] = in.nextInt();
			}
		}
		
		for(int i = 0; i < N; i++) {
			if(inp[i][0] == 1) { //add the line
				//Line l = new Line(inp[i][1], (long)inp[i][2]);
				st.add(i, rr[i], inp[i][1], inp[i][2]);
			}
		}
		
		for(int i = 0; i < N; i++) {
			if(inp[i][0] == 3) {
				long res = st.query(i, inp[i][1]);
				out.println(res == NULL ? "EMPTY SET" : res);
			}
		}
		out.close();
		
	}

	
	static class Segtree{
		int n, len;
		int[]l,r;
		CHT chts[];
		long curRes = NULL;
		public Segtree(int nn) {
			n = nn;
			len = Integer.bitCount(n) == 1 ? 2*n+1 : 4*Integer.highestOneBit(n)+1;
			//len = 4*n+1;
			l = new int[len]; r = new int[len];
			chts = new CHT[len];
			fill(1, 0, n-1);
		}
		public void fill(int i, int ll, int rr) {
			l[i] = ll;
			r[i] = rr;
			chts[i] = new CHT(1);
			if(ll == rr) return;
			int mid = (ll+rr)/2;
			fill(2*i, ll, mid);
			fill(2*i+1, mid+1, rr);
		}
		
		public void add(int l, int r, long m, long b) {
			add(1, l, r, m, b);
		}
		public void add(int i, int ll, int rr, long m, long b) {
			if(l[i] >= ll && r[i] <= rr) { 
				chts[i].add(m, b);
				return;
			}
			if(l[i] > rr || r[i] < ll || l[i] == r[i]) return;
			add(2*i, ll, rr, m, b);
			add(2*i+1, ll, rr, m, b);
		}
		public long query(int i, long x) {
			curRes = NULL;
			query(1, i, x);
			return curRes;
		}
		public void query(int i, int id, long x) {
			//System.out.println("I: "+i+"  l[i]: "+l[i]+" r[i]: "+r[i]+"  id: "+id);
			if(l[i] <= id && r[i] >= id) curRes = Math.max(curRes, chts[i].query(x));
			if(l[i] > id || r[i] < id || l[i] == r[i]) return;
			query(2*i, id, x);
			query(2*i+1, id, x);
		}
		
		
	}

	static class CHT {
		TreeSet<Line> hull;
		int type;  boolean query  = false;
		Comparator<Line> comp = new Comparator<Line>() {
			public int compare(Line a, Line b) {
				if (!query) return type * Long.compare(a.m, b.m);
				if (a.left == b.left) return Long.compare(a.m, b.m);
				return Double.compare(a.left, b.left);
			}
		};
		// -1 for min; +1 for max
		public CHT(int typee) { type = typee;  hull = new TreeSet<>(comp); }

		public void add(long m, long b) { add(new Line(m, b)); }

		public void add(Line a) {
			Line[] LR = { hull.lower(a), hull.ceiling(a) };
			for (int i = 0; i < 2; i++)
				if (LR[i] != null && LR[i].m == a.m) {
					if (type == 1 && LR[i].b >= a.b) return;
					if (type == -1 && LR[i].b <= a.b) return;
					remove(LR[i]);
				}
			hull.add(a);
			Line L = hull.lower(a), R = hull.higher(a);
			if (L != null && R != null && a.inter(R) <= R.left) {
				hull.remove(a);
				return;
			}
			Line LL = (L != null) ? hull.lower(L) : null;
			Line RR = (R != null) ? hull.higher(R) : null;
			if (L != null) a.left = a.inter(L);
			if (R != null) R.left = a.inter(R);
			while (LL != null && L.left >= a.inter(LL)) {
				remove(L);
				a.left = a.inter(L = LL);
				LL = hull.lower(L);
			}
			while (RR != null && R.inter(RR) <= a.inter(RR)) {
				remove(R);
				RR.left = a.inter(R = RR);
				RR = hull.higher(R);
			}
		}

		public long query(long x) {
			if(hull.size() == 0) return NULL;
			Line temp = new Line(0, 0, 0);
			temp.left = x;  query = true;
			long ans = (long) hull.floor(temp).eval(x);
			query = false;  return ans;
		}

		private void remove(Line x) { hull.remove(x); }

		public int size() { return hull.size(); }

		static class Line {
			long m, b; double left = Long.MIN_VALUE;
			public Line(long mm, long x, long y) { m = mm; b = -m * x + y; }
			public Line(long mm, long bb) { m = mm; b = bb; }
			public long eval(long x) { return m * x + b; }
			public double inter(Line x) {
				return (double) (x.b - this.b) / (double) (this.m - x.m);
			}
		}
	}
	
	
	static class FS{
		BufferedReader br;
		StringTokenizer st;
		public FS(String s) throws Exception {
			try{ br = new BufferedReader(new FileReader(s)); }
			catch(Exception e) { throw new Exception(); }
		}
		public FS(){
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String nextToken()	{
			while(st == null ||!st.hasMoreElements()){
				try { st = new StringTokenizer(br.readLine());}
				catch(IOException e) { e.printStackTrace(); }			
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(nextToken());
		}
		long nextLong() {
			return Long.parseLong(nextToken());
		}
		double nextDouble() {
			return Double.parseDouble(nextToken());
		}
		String next() {
			return nextToken();
		}
	}
}