Problem: Fedya and Sasha are friends, that's why Sasha knows everything about Fedya.

Fedya keeps his patience in an infinitely large bowl. But, unlike the bowl, Fedya's patience isn't infinite, that is why let v be the number of liters of Fedya's patience, and, as soon as v becomes equal to 0, the bowl will burst immediately. There is one tap in the bowl which pumps s liters of patience per second. Notice that s can be negative, in that case, the tap pumps out the patience. Sasha can do different things, so he is able to change the tap's speed. All actions that Sasha does can be represented as q queries. There are three types of queries:

  1. "1 t s" — add a new event, means that starting from the t-th second the tap's speed will be equal to s. 
  2. "2 t" — delete the event which happens at the t-th second. It is guaranteed that such event exists. 
  3. "3 l r v" — Sasha wonders: if you take all the events for which l ≤ t ≤ r and simulate changes of Fedya's patience from the very beginning of the l-th second till the very beginning of the r-th second inclusive (the initial volume of patience, at the beginning of the l-th second, equals to v liters) then when will be the moment when the bowl will burst. If that does not happen, then the answer will be -1. 



Since Sasha does not want to check what will happen when Fedya's patience ends, and he has already come up with the queries, he is asking you to help him and find the answer for each query of the 3-rd type.

It is guaranteed that at any moment of time, there won't be two events which happen at the same second.

Input

The first line contans one integer q (1 ≤ q ≤ 10^5) — the number of queries.

Each of the next q lines have one of the following formats:

  * 1 t s (1 ≤ t ≤ 10^9, -10^9 ≤ s ≤ 10^9), means that a new event is added, which means that starting from the t-th second the tap's speed will be equal to s. 
  * 2 t (1 ≤ t ≤ 10^9), means that the event which happens at the t-th second must be deleted. Guaranteed that such exists. 
  * 3 l r v (1 ≤ l ≤ r ≤ 10^9, 0 ≤ v ≤ 10^9), means that you should simulate the process from the very beginning of the l-th second till the very beginning of the r-th second inclusive, and to say when will the bowl burst. 



It is guaranteed that t, s, l, r, v in all the queries are integers.

Also, it is guaranteed that there is at least one query of the 3-rd type, and there won't be a query of the 1-st type with such t, that there already exists an event which happens at that second t.

Output

For each query of the 3-rd type, print in a new line the moment when the bowl will burst or print -1 if it won't happen.

Your answer will be considered correct if it's absolute or relative error does not exceed 10^{-6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-6}.

Examples

Input


6
1 2 1
1 4 -3
3 1 6 1
3 1 6 3
3 1 6 4
3 1 6 5


Output


5
5.666667
6
-1


Input


10
1 2 2
1 4 4
1 7 -10
3 2 4 1
3 5 6 0
3 1 15 1
2 4
3 1 15 1
1 8 1
3 1 15 1


Output


-1
5
8.7
8.1
-1


Input


5
1 1000 9999999
1 2000 -9999
3 1000 2000 0
2 1000
3 1000 2002 1


Output


1000
2000.0001

Note

In the first example all the queries of the 3-rd type cover all the events, it's simulation is following:

<image>

Solution (in JAVA):

Solution:
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Optional.*;

import java.util.*;
import java.util.stream.*;

public class C {

	private class Node {
		private final Node L, R;
		private final int from, to, m;
		private long t, S, D, B;
		private boolean U = true;

		public Node(int N) { this(0, N); }
		public void set(long S, int from, int to) {
			assert this.from <= from && from < to && to <= this.to;
			if (this.from == from && this.to == to) {
				this.S = S; U = true;
				D = S * t;
				B = min(0, D);
			}
			else {
				if (from < m)
					L.set(S, from, min(to, m));
				if (to > m)
					R.set(S, max(from, m), to);
				if (U) {
					if (this.from < from)
						L.set(this.S, this.from, min(from, m));
					if (m < from)
						R.set(this.S, m, from);
				}
				U = false;
				D = L.D + R.D;
				B = min(L.B, L.D + R.B);
			}
		}
		private double calc(long v, int from, int to) {
			assert this.from <= from && from < to && to <= this.to;
			if (this.from == from && this.to == to && v + B > 0)
				return -1;
			else if (U) {
				long dt = T[to] - T[from];
				if (v + S * dt <= 0)
					return T[from] - 1.0 * v / S;
			}
			else {
				if (from < m) {
					double left = L.calc(v, from, min(to, m));
					if (left >= -.5)
						return left;
				}
				if (to > m) {
					if (from < m)
						v += L.diff(from, m);
					assert v > 0;
					double right = R.calc(v, max(from, m), to);
					if (right >= -.5)
						return right;
				}
			}
			return -1;
		}
		private long diff(int from, int to) {
			assert this.from <= from && from < to && to <= this.to;
			if (this.from == from && this.to == to)
				return D;
			else if (U) {
				long dt = T[to] - T[from];
				return S * dt;
			}
			else {
				long res = 0;
				if (from < m)
					res += L.diff(from, min(m, to));
				if (m < to)
					res += R.diff(max(m, from), to);
				return res;
			}
		}
		private Node(int from, int to) {
			assert from < to ;
			this.from = from;
			this.to = to;
			t = T[to] - T[from];
			m = (from + to) / 2;
			if (m > from) {
				L = new Node(from, m);
				R = new Node(m, to);
			} else
				L = R = null;
		}
	}

	private int [] T;
	TreeSet<Integer> Z = new TreeSet<>();

	public Object solve () {
		int Q = sc.nextInt();
		int [][] A = sc.nextInts(Q);

		// Compress
		List<Integer> L = new ArrayList<>();
		for (int [] a : A)
			if (a[0] == 1)
				L.add(a[1]);
			else if (a[0] == 3) {
				L.add(a[1]);
				L.add(a[2]);
			}

		T = sort(unboxed(L.toArray(new Integer[0]))); L = new ArrayList<>(); L.add(T[0]);
		for (int i : rep(1, T.length))
			if (T[i] != T[i-1])
				L.add(T[i]);
		T = unboxed(L.toArray(new Integer[0]));
		int N = T.length - 1;
		
		Node S = new Node(N);
		long [] W = new long [N];

		for (int [] a : A)
			if (a[0] == 1) {
				int from = binarySearch(T, a[1]);
				int to = ofNullable(Z.higher(from)).orElse(N);
				if (from < to) {
					S.set(a[2], from, to);
					Z.add(from); W[from] = a[2];
				}
			}
			else if (a[0] == 2) {
				int at = binarySearch(T, a[1]);
				if (Z.remove(at)) {
					int from = ofNullable(Z.lower(at)).orElse(0), to = ofNullable(Z.higher(at)).orElse(N);
					S.set(W[from], from, to);
					W[at] = 0;
				}
			}
			else if (a[3] == 0)
				print(a[1]);
			else {
				int from = ofNullable(Z.ceiling(binarySearch(T, a[1]))).orElse(N);
				int to = binarySearch(T, a[2]);
				if (from >= to)
					print(-1);
				else {
					double res = S.calc(a[3], from, to);
					print(res);
				}
			}

		return null;
	}

	private static final int CONTEST_TYPE = 1;

	private static void init () {
	}

	private static Integer [] boxed (int ... A) { return stream(A).mapToObj(x -> x).toArray(Integer[]::new); }
	private static int [] rep (int S, int T) { if (S >= T) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	private static int [] sort (int [] A) { Integer [] AA = boxed(A); Collections.shuffle(asList(AA)); Arrays.sort(unboxed(AA, A)); return A; }
	private static int [] unboxed (Integer [] A) { return stream(A).mapToInt(x -> x).toArray(); }
	private static int [] unboxed (Integer [] A, int [] a) { System.arraycopy(unboxed(A), 0, a, 0, A.length); return a; }
	//////////////////////////////////////////////////////////////////////////////////// OFF
	private static IOUtils.MyScanner sc = new IOUtils.MyScanner();
	private static Object print (Object o, Object ... A) { IOUtils.print(o, A); return null; }
	private static class IOUtils {
		public static class MyScanner {
			public String next () { newLine(); return line[index++]; }
			public int nextInt () { return Integer.parseInt(next()); }
			public String nextLine () { line = null; return readLine(); }
			public String [] nextStrings () { return split(nextLine()); }
			public int[] nextInts () { return nextStream().mapToInt(Integer::parseInt).toArray(); }
			public int[][] nextInts (int N) { return IntStream.range(0, N).mapToObj(i -> nextInts()).toArray(int[][]::new); }
			//////////////////////////////////////////////
			private boolean eol () { return index == line.length; }
			private String readLine () {
				try {
					return r.readLine();
				} catch (Exception e) {
					throw new Error (e);
				}
			}
			private final java.io.BufferedReader r;
			private MyScanner () { this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in))); }
			private MyScanner (java.io.BufferedReader r) {
				try {
					this.r = r;
					while (!r.ready())
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}
			private String [] line;
			private int index;
			private void newLine () {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}
			private java.util.stream.Stream<String> nextStream () { return java.util.Arrays.stream(nextStrings()); }
			private String [] split (String s) { return s.length() > 0 ? s.split(" ") : new String [0]; }
		}
		private static String build (Object o, Object ... A) { return buildDelim(" ", o, A); }
		private static String buildDelim (String delim, Object o, Object ... A) {
			StringBuilder b = new StringBuilder();
			append(b, o, delim);
			for (Object p : A)
				append(b, p, delim);
			return b.substring(delim.length());
		}
		//////////////////////////////////////////////////////////////////////////////////
		private static final java.text.DecimalFormat formatter = new java.text.DecimalFormat("#.#########");
		private static void start () { if (t == 0) t = millis(); }
		private static void append (java.util.function.Consumer<Object> f, java.util.function.Consumer<Object> g, final Object o) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					f.accept(java.lang.reflect.Array.get(o, i));
			}
			else if (o instanceof Iterable<?>)
				((Iterable<?>)o).forEach(f::accept);
			else
				g.accept(o instanceof Double ? formatter.format(o) : o);
		}
		private static void append (final StringBuilder b, Object o, final String delim) {
			append(x -> { append(b, x, delim); }, x -> b.append(delim).append(x), o);
		}
		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
		private static void print (Object o, Object ... A) {
			String res = build(o, A);
			if (DEBUG == 2)
				err(res, '(', time(), ')');
			pw.println(res);
			if (DEBUG == 1) {
				pw.flush();
				System.out.flush();
			}
		}
		private static void err (Object o, Object ... A) { System.err.println(build(o, A)); }
		private static int DEBUG;
		private static void exit () {
			String end = "------------------" + System.lineSeparator() + time();
			switch(DEBUG) {
			case 1: print(end); break;
			case 2: err(end); break;
			}
			IOUtils.pw.close();
			System.out.flush();
			System.exit(0);
		}
		private static long t;
		private static long millis () { return System.currentTimeMillis(); }
		private static String time () { return "Time: " + (millis() - t) / 1000.0; }
		private static void run (int N) {
			try { DEBUG = Integer.parseInt(System.getProperties().get("DEBUG").toString()); }
			catch (Throwable t) {}

			for (int n = 1; n <= N; ++n) {
				Object res = new C().solve();
				if (res != null) {
					@SuppressWarnings("all")
					Object o = CONTEST_TYPE == 0 ? "Case #" + n + ": " + build(res) : res;
					print(o);
				}
			}
			exit();
		}
	}
	////////////////////////////////////////////////////////////////////////////////////
	public static void main (String[] args) {
		init();
		@SuppressWarnings("all")
		int N = CONTEST_TYPE == 1 ? 1 : sc.nextInt();
		IOUtils.run(N);
	}
}