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], l);
			}
		}
		
		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;
		MaxConvexHull 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 MaxConvexHull[len];
			fill(1, 0, n-1);
		}
		public void fill(int i, int ll, int rr) {
			l[i] = ll;
			r[i] = rr;
			chts[i] = new MaxConvexHull();
			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, Line line) {
			add(1, l, r, line);
		}
		public void add(int i, int ll, int rr, Line line) {
			if(l[i] >= ll && r[i] <= rr) { 
				chts[i].add(line.m, line.b);
				return;
			}
			if(l[i] > rr || r[i] < ll || l[i] == r[i]) return;
			add(2*i, ll, rr, line);
			add(2*i+1, ll, rr, line);
		}
		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 int compT;
	static long oo = Long.MIN_VALUE;
	static 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);
		}

	}
	static 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);
			}
		}
	}
	/*
	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);
				//R.left = L.inter(R);
				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;
			Line extra = hull.floor(temp);
			if(extra == null) {
				System.out.println(hull.size());
				for(Line line : hull) {
					System.out.println(line);
				}
				System.out.println(hull.first());
				System.out.println();
			}
			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);
		}
		@Override
		public String toString() {
			return "("+m+", "+b+")";
		}
	}
	
	 */
	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();
		}
	}
}