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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Arrays;
import java.io.BufferedInputStream;
import java.util.concurrent.Callable;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Collections;
import java.io.InputStream;

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

	static class TaskF {
		public void solve(int testNumber, BufferedInputStream _in, PrintWriter out) {

			InputReader in = new InputReader(_in);
			long startTime = System.currentTimeMillis();
			int nt = 1;
			Task t = new Task(1);
			t.readInput(in);
			t.call();
			t.writeOutput(out);
			in.close();
			System.err.println("Time: " + (System.currentTimeMillis() - startTime) + " miliseconds");
		}

	}

	static class StaticConvexHullTrickMaxAscent {
		ArrayList<StaticConvexHullTrickMaxAscent.Li> hull;
		StaticConvexHullTrickMaxAscent.Li queryLine;

		public StaticConvexHullTrickMaxAscent() {

			hull = new ArrayList<>();
			queryLine = new StaticConvexHullTrickMaxAscent.Li(0, 0, 0, 0);

		}

		void intersect(StaticConvexHullTrickMaxAscent.Li l1, StaticConvexHullTrickMaxAscent.Li l2, StaticConvexHullTrickMaxAscent.Li ret) {
			ret.ax = (l1.b - l2.b);
			ret.bx = (l2.a - l1.a);
			if (DynamicConvexHullTrickMin.CHECK_OVERFLOW) {
				//ret.reduce();
				long g = LongMath.gcd(Math.abs(ret.ax), Math.abs(ret.bx));
				if (ret.bx < 0) g = -g;
				ret.ax /= g;
				ret.bx /= g;
			} else {
				if (ret.bx < 0) {
					ret.ax = -ret.ax;
					ret.bx = -ret.bx;
				}
			}
		}

		boolean bad(StaticConvexHullTrickMaxAscent.Li l1, StaticConvexHullTrickMaxAscent.Li l2, StaticConvexHullTrickMaxAscent.Li l3) {
			if (DynamicConvexHullTrickMin.CHECK_OVERFLOW) {
				long a1 = l2.b - l1.b;
				long b1 = l1.a - l2.a;

				long a2 = l3.b - l1.b;
				long b2 = l1.a - l3.a;


				long g = LongMath.gcd(Math.abs(a1), Math.abs(b1));
				if (b1 < 0) g = -g;
				a1 /= g;
				b1 /= g;

				g = LongMath.gcd(Math.abs(a2), Math.abs(b2));
				if (b2 < 0) g = -g;
				a2 /= g;
				b2 /= g;

				if (a1 == a2 && b1 == b2) return true;
				return !Rational.checkLessRational(a2, b2, a1, b1);
			} else {
				return ((l3.b - l1.b) * (l1.a - l2.a)) >= ((l2.b - l1.b) * (l1.a - l3.a));
			}

		}

		void addLine(long a, long b) {
			int sz = hull.size();
			if (sz > 0 && a == hull.get(sz - 1).a) {
				if (b == hull.get(sz - 1).b) return;
				if (b < hull.get(sz - 1).b) return;
				hull.remove(sz - 1);
				sz--;
			}
			StaticConvexHullTrickMaxAscent.Li line = new StaticConvexHullTrickMaxAscent.Li(a, b, Long.MIN_VALUE + 2, 1);

			while (sz >= 2 && bad(line, hull.get(sz - 1), hull.get(sz - 2))) {
				hull.remove(sz - 1);
				sz--;
			}
			hull.add(line);
			sz++;
			if (sz > 1) {
				intersect(hull.get(sz - 1), hull.get(sz - 2), hull.get(sz - 1));
			}

		}

		public long query(long xx) {

			if (hull.size() == 0) throw new RuntimeException();
			queryLine.x = xx;
			int low = MathUtils.lowerBound(hull, 0, hull.size(), queryLine, new Comparator<StaticConvexHullTrickMaxAscent.Li>() {

				public int compare(StaticConvexHullTrickMaxAscent.Li o1, StaticConvexHullTrickMaxAscent.Li o2) {

					if (DynamicConvexHullTrickMin.CHECK_OVERFLOW) {
						int ret = -1;
						if (o1.x == o2.ax && o2.bx == 1) ret = 1;
						else if (!Rational.checkLessRational(o1.x, 1, o2.ax, o2.bx)) ret = 1;
						return ret;
					} else {
						return Long.compare((o1.x * o2.bx), o2.ax);
					}

				}
			}) - 1;
			return hull.get(low).calc(xx);
		}

		public static class Li {
			long a;
			long b;
			long ax;
			long bx;
			long x;

			public Li(long a, long b, long ax, long bx) {
				this.a = a;
				this.b = b;
				this.ax = ax;
				this.bx = bx;
			}

			long calc(long x) {
				return a * x + b;
			}

		}

	}

	static class MathUtils {
		public static <T> int lowerBound(ArrayList<T> a, int first, int last, T key, Comparator<T> cmp) {
			int count = last - first, step;
			int it;
			while (count > 0) {
				it = first;
				step = count / 2;
				it += step;
				//int _cmp = a.get(it).compareTo(key);
				int _cmp = -cmp.compare(key, a.get(it));
				if (_cmp < 0) {
					first = ++it;
					count -= step + 1;
				} else
					count = step;
			}
			return first;
		}

	}

	static class Rational implements Comparable<Rational> {
		private long a;
		private long b;

		public long getA() {
			return a;
		}

		public long getB() {
			return b;
		}

		public Rational() {
			a = 0;
			b = 1;
		}

		public static boolean checkLessRational(long a1, long b1, long a2, long b2) {
			long tsn = a1;
			long tsd = b1;
			long tsq = a1 / b1;
			long tsr = a1 % b1;

			long rsn = a2;
			long rsd = b2;
			long rsq = a2 / b2;
			long rsr = a2 % b2;

			int reverse = 0;


			while (tsr < 0) {
				tsr += tsd;
				--tsq;
			}
			while (rsr < 0) {
				rsr += rsd;
				--rsq;
			}

			// Loop through and compare each variable's continued-fraction components
			for (; ; ) {
				// The quotients of the current cycle are the continued-fraction
				// components.  Comparing two c.f. is comparing their sequences,
				// stopping at the first difference.
				if (tsq != rsq) {
					// Since reciprocation changes the relative order of two variables,
					// and c.f. use reciprocals, the less/greater-than test reverses
					// after each index.  (Start w/ non-reversed @ whole-number place.)
					return reverse != 0 ? tsq > rsq : tsq < rsq;
				}

				// Prepare the next cycle
				reverse ^= 1;

				if ((tsr == 0) || (rsr == 0)) {
					// At least one variable's c.f. expansion has ended
					break;
				}

				tsn = tsd;
				tsd = tsr;
				tsq = tsn / tsd;
				tsr = tsn % tsd;
				rsn = rsd;
				rsd = rsr;
				rsq = rsn / rsd;
				rsr = rsn % rsd;
			}

			// Compare infinity-valued components for otherwise equal sequences
			if (tsr == rsr) {
				// Both remainders are zero, so the next (and subsequent) c.f.
				// components for both sequences are infinity.  Therefore, the sequences
				// and their corresponding values are equal.
				return false;
			} else {

				// Exactly one of the remainders is zero, so all following c.f.
				// components of that variable are infinity, while the other variable
				// has a finite next c.f. component.  So that other variable has the
				// lesser value (modulo the reversal flag!).
				return (tsr != 0) != (reverse != 0);

			}
		}

		public Rational(long a, long b) {
			this.a = a;
			this.b = b;
			if (b == 0) throw new RuntimeException();
			reduce();
		}

		public void reduce() {
			long g = LongMath.gcd(Math.abs(a), Math.abs(b));
			if (b < 0) g = -g;
			this.a /= g;
			this.b /= g;
		}


		public int compareTo(Rational o) {
			int ret = -1;
			if (a == o.a && b == o.b) ret = 0;
			else if (!checkLessRational(a, b, o.a, o.b)) ret = 1;

			return ret;
			//return Long.compare(LongMath.checkedMultiply(this.a, o.b), LongMath.checkedMultiply(o.a, this.b));
		}


		public String toString() {
			return +a + "/" + b;
		}


		public int hashCode() {
			return Long.hashCode(a) ^ Long.hashCode(b);
		}

		public boolean equals(Object obj) {
			if (obj instanceof Rational) {
				return this.compareTo((Rational) obj) == 0;
			}
			return false;
		}

	}

	static class SegmentData {
		int a;
		int b;
		StaticConvexHullTrickMaxAscent cv = new StaticConvexHullTrickMaxAscent();

		public SegmentData(int a, int b) {
			this.a = a;
			this.b = b;
		}

	}

	static class DynamicConvexHullTrickMin {
		public static final boolean CHECK_OVERFLOW = false;
		private DynamicConvexHullTrickMin.Line forQueryLine;

		public DynamicConvexHullTrickMin() {
			forQueryLine = new DynamicConvexHullTrickMin.Line(0, 0);
			forQueryLine.isQuery = true;
		}

		static class Line implements Comparable<DynamicConvexHullTrickMin.Line> {
			long a;
			long b;
			Rational p;
			boolean isQuery = false;
			long x = 0;

			public Line(long a, long b) {
				this.a = a;
				this.b = b;
			}


			public int compareTo(DynamicConvexHullTrickMin.Line o) {
				if (isQuery) {
					if (CHECK_OVERFLOW) {
						int ret = -1;
						if (x == o.p.getA() && o.p.getB() == 1) ret = 1;
						else if (!Rational.checkLessRational(x, 1, o.p.getA(), o.p.getB())) ret = 1;
						return ret;
					} else {
						return Long.compare((x * o.p.getB()), o.p.getA());
					}
				} else {
					return Long.compare(o.a, a);

				}
			}


			public String toString() {
				return "Line{" +
						"a=" + a +
						", b=" + b +
						'}';
			}

		}

	}

	static class Task implements Callable<Task> {
		ArrayList<Triple<Integer, Integer, Integer>> listLine = new ArrayList<>();
		int[] end;
		int[] type;
		int[] q;
		int n;
		int testNumber;

		public void readInput(InputReader in) {
	/* read input here */
			n = in.nextInt();
			end = new int[n];
			q = new int[n];
			type = new int[n];
			Arrays.fill(end, n);

			for (int i = 0; i < n; ++i) {
				type[i] = in.nextInt();


				switch (type[i]) {
					case 1: {
						Triple<Integer, Integer, Integer> li = new Triple<>(in.nextInt(), in.nextInt(), i);
						listLine.add(li);
					}
					break;
					case 2: {
						q[i] = in.nextInt() - 1;
						end[q[i]] = i;

					}
					break;

					case 3: {
						q[i] = in.nextInt();

					}
					break;
				}
			}
		}

		public Task call() {
	/* process main algorithm here */

			return this;
		}

		public void writeOutput(PrintWriter out) {

			SegmentTree st = new SegmentTree(n);
			Collections.sort(listLine);
			for (Triple<Integer, Integer, Integer> trip : listLine) {
				st.update(1, 0, st.sz - 1, trip.third, end[trip.third], trip.first.longValue(), trip.second.longValue());
			}

			for (int i = 0; i < n; ++i)
				if (type[i] == 3) {
					long ret = st.query(1, 0, st.sz - 1, i, i, q[i]);
					if (ret == Long.MIN_VALUE) out.println("EMPTY SET");
					else out.println(ret);
				}
			System.err.println("Test case: " + testNumber + " done!");

			//out.print(sb.toString());
		}

		Task(int testNumber) {
			this.testNumber = testNumber;
		}

	}

	static final class LongMath {
		public static long gcd(long a, long b) {
	/*
     * The reason we require both arguments to be >= 0 is because otherwise, what do you return on
     * gcd(0, Long.MIN_VALUE)? BigInteger.gcd would return positive 2^63, but positive 2^63 isn't an
     * int.
     */
			MathPreconditions.checkNonNegative("a", a);
			MathPreconditions.checkNonNegative("b", b);
			if (a == 0) {
				// 0 % b == 0, so b divides a, but the converse doesn't hold.
				// BigInteger.gcd is consistent with this decision.
				return b;
			} else if (b == 0) {
				return a; // similar logic
			}
    /*
     * Uses the binary GCD algorithm; see http://en.wikipedia.org/wiki/Binary_GCD_algorithm. This is
     * >60% faster than the Euclidean algorithm in benchmarks.
     */
			int aTwos = Long.numberOfTrailingZeros(a);
			a >>= aTwos; // divide out all 2s
			int bTwos = Long.numberOfTrailingZeros(b);
			b >>= bTwos; // divide out all 2s
			while (a != b) { // both a, b are odd
				// The key to the binary GCD algorithm is as follows:
				// Both a and b are odd. Assume a > b; then gcd(a - b, b) = gcd(a, b).
				// But in gcd(a - b, b), a - b is even and b is odd, so we can divide out powers of two.

				// We bend over backwards to avoid branching, adapting a technique from
				// http://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax

				long delta = a - b; // can't overflow, since a and b are nonnegative

				long minDeltaOrZero = delta & (delta >> (Long.SIZE - 1));
				// equivalent to Math.min(delta, 0)

				a = delta - minDeltaOrZero - minDeltaOrZero; // sets a to Math.abs(a - b)
				// a is now nonnegative and even

				b += minDeltaOrZero; // sets b to min(old a, b)
				a >>= Long.numberOfTrailingZeros(a); // divide out all 2s, since 2 doesn't divide b
			}
			return a << Math.min(aTwos, bTwos);
		}

		private LongMath() {
		}

	}

	static class Triple<T1 extends Comparable<T1>, T2 extends Comparable<T2>, T3 extends Comparable<T3>> implements Comparable<Triple<T1, T2, T3>> {
		public T1 first;
		public T2 second;
		public T3 third;

		public Triple(T1 first, T2 second, T3 third) {
			this.first = first;
			this.second = second;
			this.third = third;
		}


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


		public int compareTo(Triple<T1, T2, T3> o) {
			int t = first.compareTo(o.first);
			if (t != 0) return t;
			t = second.compareTo(o.second);
			if (t != 0) return t;
			return third.compareTo(o.third);
		}


		public int hashCode() {
			return first.hashCode() ^ second.hashCode() ^ third.hashCode();
		}

		public boolean equals(Object obj) {
			if (obj instanceof Triple) {
				Triple p = (Triple) obj;
				return first.equals(p.first) && second.equals(p.second) && third.equals(p.third);
			}
			return false;
		}

	}

	static class SegmentTree {
		SegmentData[] data;
		int sz;

		SegmentTree(int n) {
			for (sz = 1; sz < n; sz <<= 1) ;
			data = new SegmentData[2 * sz];
			init(1, 0, sz - 1);

		}

		public void init(int node, int b, int e) {
			if (e > b) {
				init(2 * node, b, (b + e) / 2);
				init(2 * node + 1, (b + e) / 2 + 1, e);
			}
			data[node] = new SegmentData(b, e);
		}

		public void update(int node, int b, int e, int ii, int jj, long la, long lb) {
			if (ii > e || jj < b) {
				return;
			}

			if (b >= ii && e <= jj) {
				data[node].cv.addLine(la, lb);
				return;
			}

			int left = 2 * node;
			int right = left + 1;


			update(left, b, (b + e) / 2, ii, jj, la, lb);
			update(right, (b + e) / 2 + 1, e, ii, jj, la, lb);
		}

		public long query(int node, int b, int e, int ii, int jj, long x) {
			if (ii > e || jj < b) {
				return Long.MIN_VALUE;
			}

			if (b >= ii && e <= jj) {
				if (data[node].cv.hull.size() > 0) return data[node].cv.query(x);
				return Long.MIN_VALUE;
			}

			int left = 2 * node;
			int right = left + 1;
			long temp = Long.MIN_VALUE;
			if (data[node].cv.hull.size() > 0)
				temp = data[node].cv.query(x);

			return Math.max(temp, Math.max(query(left, b, (b + e) / 2, ii, jj, x), query(right, (b + e) / 2 + 1, e, ii, jj, x)));
		}

	}

	static final class MathPreconditions {
		static long checkNonNegative(String role, long x) {
			if (x < 0) {
				throw new IllegalArgumentException(role + " (" + x + ") must be >= 0");
			}
			return x;
		}

		private MathPreconditions() {
		}

	}

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public static boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public void close() {

		}

	}
}