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.util.*;
import java.io.*;
/*
7
3 1
1 2 3
3 1
1 -1 100
3 1
2 4
3 1


48
3 -99
1 -1 32
2 2
1 -18 -86
2 4
3 -32
1 -21 -38
1 -60 -96
3 37
2 8
3 56
3 -72
1 -91 -7
1 21 -41
3 -59
3 -12
3 -33
3 -75
3 -7
2 7
2 14
2 13
3 -49
1 -79 -94
2 24
1 37 -39
3 60
3 93
2 26
1 34 72
3 -73
1 42 76
3 -17
1 64 64
1 17 -90
2 32
2 30
3 60
2 35
1 78 1
1 52 -28
1 -37 -28
2 34
1 -94 -41
3 93
1 74 56
2 44
3 -32
1156
 */
public class K
{
	public static void main(String[] arg) throws IOException
	{
		new K();
	}
	public K() throws IOException
	{
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = in.nextInt();
		int[] op = new int[n];
		int[] m = new int[n];
		int[] b = new int[n];
		int[] inT = new int[n];
		int[] outT = new int[n];
		Arrays.fill(outT, n-1);
		int[] x = new int[n];
		for(int i = 0; i < n; i++)
		{
			op[i] = in.nextInt();
			if(op[i] == 1)
			{
				m[i] = in.nextInt();
				b[i] = in.nextInt();
				inT[i] = i;
			}
			else if(op[i] == 2)
			{
				outT[in.nextInt()-1] = i;
			}
			else
			{
				x[i] = in.nextInt();
			}
		}
		ST st = new ST(n);
		for(int i = 0; i < n; i++)
		{
			if(op[i] == 1)
			{
				st.update(inT[i], outT[i], new Line(m[i], b[i]));
			}
		}
		for(int i = 0; i < n; i++)
		{
			if(op[i] == 3)
			{
				long v = st.query(i, i, x[i]);
				if(v == oo) out.println("EMPTY SET");
				else out.println(v);
			}
		}
		in.close(); out.close();
	}
	class ST
	{
		MaxConvexHull[] vs;
		int s;
		public ST(int size)
		{
			s = size;
			vs = new MaxConvexHull[4*size+1];
			//build(0, s-1, 1);
		}
//		void build(int li, int ri, int c)
//		{
//			if(li == ri)
//			{
//				vs[c] = new MaxConvexHull();
//				return;
//			}
//			int m = li+(ri-li)/2;
//			build(li, m, 2*c);
//			build(m+1, ri, 2*c+1);
//			vs[c] = new MaxConvexHull();
//		}
		
		void update(int l, int r, Line v)
		{
			update(l, r, v, 0, s-1, 1);
		}
		
		void update(int lq, int rq, Line v, int li, int ri, int c)
		{
			if(rq < li || ri < lq) return;
			if(lq <= li && ri <= rq)
			{
				if(vs[c] == null) vs[c] = new MaxConvexHull();
				vs[c].add(v.m, v.b);
				return;
			}
			int m = li + (ri-li)/2;
			update(lq, rq, v, li, m, 2*c);
			update(lq, rq, v, m+1, ri, 2*c+1);
		}
		
		long query(int l, int r, long x)
		{
			return query(l, r, x, 0, s-1, 1);
		}
		long query(int lq, int rq, long x, int li, int ri, int c)
		{
			if(rq < li || ri < lq) return oo;
			if(lq <= li && ri <= rq)
			{
				if(vs[c] == null) return oo;
				return vs[c].query(x);
			}
			int m = li + (ri-li)/2;
			long op1 = query(lq, rq, x, li, m, 2*c);
			long op2 = query(lq, rq, x, m+1, ri, 2*c+1);
			if(vs[c] != null)
				return Math.max(Math.max(op1, op2), vs[c].query(x));
			else return Math.max(op1, op2);
		}
	}
	class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;
		public FastScanner(InputStream in)
		{
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer("");
		}
		public String next() throws IOException
		{
			while(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}
		public void close() throws IOException
		{
			br.close();
		}
	}
	class Line implements Comparable<Line>
	{
		long m, b;
		double ot;
		public Line(long aa, long bb)
		{
			m = aa;
			b = bb;
			ot = oo;
		}
		public Line(double o)
		{
			ot = o;
			m = Long.MAX_VALUE;
			b = Long.MAX_VALUE;
		}
		public int compareTo(Line l)
		{
			if(compT == 0)
			{
				if(m != l.m) return Long.compare(m, l.m);
				else return Long.compare(b, l.b);
			}
			else
			{
				return Double.compare(ot, l.ot);
			}
		}
	}
	long oo = Long.MIN_VALUE;
	int compT;
	class MaxConvexHull
	{
		// 0 slope, 1 x-intersection
		TreeSet<Line> ts;
		public MaxConvexHull()
		{
			ts = new TreeSet<Line>();
			compT = 0;
		}
		void add(long m, long b)
	    {
	        Line cur = new Line(m, b);
	        ts.add(cur);
	        if(ts.size() == 2)
	        {
	        	Line top = ts.last();
	        	Line bot = ts.first();
	        	if(top.m == bot.m)
	        	{
	        		if(top.b >= bot.b) ts.remove(bot);
	        		else ts.remove(top);
	        		ts.first().ot = oo;
	        	}
	        }
	        Line below1 = ts.lower(cur);
	        Line below2 = null;
	        if(below1 != null) below2 = ts.lower(below1);
	        while(below1 != null && below2 != null && bad(below2, below1, cur))
	        {
	            ts.remove(below1);
	            below1 = below2;
	            below2 = ts.lower(below1);
	        }
	        Line above1 = ts.higher(cur);
	        Line above2 = null;
	        if(above1 != null) above2 = ts.higher(above1);
	        while(above1 != null && above2 != null && bad(cur, above1, above2))
	        {
	            ts.remove(above1);
	            above1 = above2;
	            above2 = ts.higher(above1);
	        }
	        Line below3 = ts.lower(cur);
	        Line above3 = ts.higher(cur);
	        while(below3 != null && above3 != null && bad(below3, cur, above3))
	        {
	            Line temp = above3;
	            ts.remove(cur);
	            cur = temp;
	            above3 = ts.higher(cur);
	        }
	        Line below = ts.lower(cur);
	        Line above = ts.higher(cur);
	        if(below != null) cur.ot = (double)(cur.b-below.b)/(double)(below.m-cur.m);
	        if(above != null) above.ot = (double)(above.b-cur.b)/(double)(cur.m-above.m);
	        if(ts.size() == 2)
	        {
	        	Line top = ts.last();
	        	Line bot = ts.first();
	        	if(top.m == bot.m)
	        	{
	        		if(top.b >= bot.b) ts.remove(bot);
	        		else ts.remove(top);
	        		ts.first().ot = oo;
	        	}
	        }
	    }
		long query(long x)
		{
			compT = 1;			
			Line l = ts.floor(new Line(x));
			compT = 0;
			if(l == null) return oo;
			return l.m*x+l.b;
		}
		boolean bad(Line l1, Line l2, Line l3)
		{
			return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m);
		}

	}
}

/*

 */