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 CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template <class T = int>
inline T readInt();
inline double readDouble();
inline int readUInt();
inline int readChar();
inline void readWord(char *s);
inline bool readLine(char *s);
inline bool isEof();
inline int getChar();
inline int peekChar();
inline bool seekEof();
inline void skipBlanks();
inline std::string readString();
template <class T>
inline void writeInt(T x, char end = 0, int len = -1);
inline void writeChar(int x);
inline void writeWord(const char *s);
inline void writeDouble(double x, int len = 0);
inline void flush();
static struct buffer_flusher_t {
  ~buffer_flusher_t() { flush(); }
} buffer_flusher;
using namespace std;
inline void init() {
  srand(time(0));
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
template <class T, class S>
inline void rmax(T &a, S b) {
  a = max(a, (T)b);
}
template <class T, class S>
inline void rmin(T &a, S b) {
  a = min(a, (S)b);
}
inline long long mul(long long a, long long b, long long m) {
  return a * b % m;
}
inline long long binpow(long long n, long long p, long long m) {
  if (!p) return 1;
  if (p & 1) return mul(n, binpow(n, p - 1, m), m);
  long long v = binpow(n, p / 2, m);
  return mul(v, v, m);
}
inline bool is_prime(long long n) {
  for (long long i = 2; i * i <= n; ++i)
    if (n % i == 0) return 0;
  return 1;
}
inline vector<long long> factor(long long n) {
  vector<long long> ans;
  for (long long i = 2; i * i <= n; ++i)
    while (n % i == 0) ans.push_back(i), n /= i;
  if (n != 1) ans.push_back(n);
  return ans;
}
inline vector<long long> divisors(long long n) {
  vector<long long> ret;
  for (long long i = 1; i * i <= n; ++i) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  return ret;
}
inline vector<pair<long long, int>> factor_pows(long long n) {
  auto fac = factor(n);
  vector<pair<long long, int>> ret;
  int L = 0;
  while (L < (int)fac.size()) {
    int R = L;
    while (R < (int)fac.size() && fac[R] == fac[L]) ++R;
    ret.push_back({fac[L], R - L});
    L = R;
  }
  return ret;
}
inline long long gen_random_prime(long long L = (int)1e9) {
  L += rand() % 4242;
  while (!is_prime(L)) ++L;
  return L;
}
inline long long nmod(long long a, long long m) { return (a % m + m) % m; }
inline int mrand() { return abs((1LL * rand() << 15) + rand()); }
struct HashedString {
  string s;
  vector<long long> MOD, POW;
  vector<vector<long long>> hash;
  vector<vector<long long>> pows;
  string substr(int L, int n) { return s.substr(L, n); }
  int size() const { return s.size(); }
  char operator[](int n) const { return s[n]; }
  vector<long long> get_hash(int L, int R) {
    vector<long long> ret;
    for (int i = 0; i < (int)hash.size(); ++i) {
      ret.push_back(nmod(hash[i][R] - hash[i][L] * pows[i][R - L], MOD[i]));
    }
    return ret;
  }
  bool equal(int L1, int R1, int L2, int R2) {
    return get_hash(L1, R1) == get_hash(L2, R2);
  }
  void operator+=(char c) {
    s += c;
    for (int i = 0; i < (int)hash.size(); ++i) {
      long long m = MOD[i], p = POW[i], cp = pows[i].back(),
                cm = hash[i].back();
      cm = (cm * p + c) % m, cp = cp * p % m;
      hash[i].push_back(cm);
      pows[i].push_back(cp);
    }
  }
  void operator+=(const string &oth) {
    for (int i = 0; i < (int)hash.size(); ++i)
      for (char c : oth) (*this) += c;
  }
  HashedString(const string &s, int n = 1) {
    for (int i = 0; i < n; ++i) {
      MOD.push_back(gen_random_prime());
      POW.push_back(gen_random_prime());
      hash.push_back({0}), pows.push_back({1});
    }
    (*this) += s;
  }
};
const int MAXN = 3e5 + 42;
int n;
struct Treap {
  Treap *left = NULL;
  Treap *right = NULL;
  long long t;
  int y;
  long long prefix_sum;
  long long speed;
  long long push = 0;
  long long min_prefix_sum_in_subtree;
  Treap(long long t, long long val, long long speed)
      : t(t),
        y(mrand()),
        prefix_sum(val),
        speed(speed),
        min_prefix_sum_in_subtree(val) {}
};
typedef Treap *treap;
inline void vertex_add(treap a, long long push) {
  a->prefix_sum += push;
  a->min_prefix_sum_in_subtree += push;
  a->push += push;
}
inline void push(treap a) {
  long long push = a->push;
  if (!push) return;
  if (a->left) {
    vertex_add(a->left, push);
  }
  if (a->right) {
    vertex_add(a->right, push);
  }
  a->push = 0;
}
const long long INF = 1e18;
inline long long smin(treap a) {
  return a ? a->min_prefix_sum_in_subtree : INF;
}
inline void recalc(treap a) {
  a->min_prefix_sum_in_subtree =
      min({smin(a->left), smin(a->right), a->prefix_sum});
}
inline treap merge(treap a, treap b) {
  if (!a) return b;
  if (!b) return a;
  if (a->y < b->y) {
    push(a);
    a->right = merge(a->right, b);
    recalc(a);
    return a;
  } else {
    push(b);
    b->left = merge(a, b->left);
    recalc(b);
    return b;
  }
}
inline pair<treap, treap> split(treap a, long long k) {
  if (!a) return {a, a};
  push(a);
  if (a->t < k) {
    auto [l, r] = split(a->right, k);
    a->right = l;
    recalc(a);
    return {a, r};
  } else {
    auto [l, r] = split(a->left, k);
    a->left = r;
    recalc(a);
    return {l, a};
  }
}
inline treap get_least(treap a) {
  push(a);
  if (!a->left) {
    return a;
  }
  return get_least(a->left);
}
inline treap get_greatest(treap a) {
  push(a);
  if (!a->right) {
    return a;
  }
  return get_greatest(a->right);
}
inline treap find_first_less(treap a, long long v) {
  push(a);
  if (smin(a->left) <= v) {
    return find_first_less(a->left, v);
  }
  if (a->prefix_sum <= v) return a;
  return find_first_less(a->right, v);
}
inline void print_tree(treap a) {
  if (!a) return;
  print_tree(a->left);
  if (false) cerr << a->t << ' ';
  print_tree(a->right);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.precision(20);
  srand(time(0));
  treap root = new Treap(0, 0, 0);
  root = merge(root, new Treap(2e9, 0, 0));
  int q = readInt();
  int t;
  int second, type;
  for (int i = 0; i < q; ++i) {
    type = readInt();
    if (type == 1) {
      t = readInt();
      second = readInt();
      auto [l, r] = split(root, t);
      treap vr = get_least(r);
      treap vl = get_greatest(l);
      long long psum = vl->prefix_sum + (t - vl->t) * vl->speed;
      long long new_psum = psum + (vr->t - t) * second;
      vertex_add(r, new_psum - vr->prefix_sum);
      root = merge(l, merge(new Treap(t, psum, second), r));
    } else if (type == 2) {
      t = readInt();
      auto [l, tr] = split(root, t);
      auto [y, r] = split(tr, t + 1);
      treap vl = get_greatest(l);
      treap vr = get_least(r);
      long long new_psum = vl->prefix_sum + (vr->t - vl->t) * vl->speed;
      vertex_add(r, new_psum - vr->prefix_sum);
      root = merge(l, r);
    } else {
      int L = readInt();
      int R = readInt();
      long long v = readInt();
      if (v == 0) {
        cout << L << '\n';
        continue;
      }
      auto [l, yr] = split(root, L);
      auto [y, r] = split(yr, R + 1);
      if (!y) {
        cout << -1 << '\n';
      } else {
        treap vl = get_least(y);
        treap vr = get_greatest(y);
        long long searching_v = vl->prefix_sum - v;
        if (y->min_prefix_sum_in_subtree > searching_v) {
          long long new_psum = vr->prefix_sum + (R - vr->t) * vr->speed;
          if (new_psum > searching_v) {
            cout << "-1\n";
          } else {
            cout << vr->t +
                        (long double)(searching_v - vr->prefix_sum) / vr->speed
                 << '\n';
          }
        } else {
          treap h = find_first_less(y, searching_v);
          auto [yl, yr] = split(y, h->t);
          treap vyl = get_greatest(yl);
          cout << vyl->t +
                      (long double)(searching_v - vyl->prefix_sum) / vyl->speed
               << '\n';
          y = merge(yl, yr);
        }
      }
      root = merge(l, merge(y, r));
    }
  }
}
static const int buf_size = 4096;
static unsigned char buf[buf_size];
static int buf_len = 0, buf_pos = 0;
inline string readString() {
  const int MAX = 1e6 + 42;
  static char buf[MAX];
  readWord(buf);
  return string(buf);
}
inline bool isEof() {
  if (buf_pos == buf_len) {
    buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin);
    if (buf_pos == buf_len) return 1;
  }
  return 0;
}
inline int getChar() { return isEof() ? -1 : buf[buf_pos++]; }
inline int peekChar() { return isEof() ? -1 : buf[buf_pos]; }
inline bool seekEof() {
  int c;
  while ((c = peekChar()) != -1 && c <= 32) buf_pos++;
  return c == -1;
}
inline void skipBlanks() {
  while (!isEof() && buf[buf_pos] <= 32U) buf_pos++;
}
inline int readChar() {
  int c = getChar();
  while (c != -1 && c <= 32) c = getChar();
  return c;
}
inline int readUInt() {
  int c = readChar(), x = 0;
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return x;
}
template <class T>
inline T readInt() {
  int second = 1, c = readChar();
  T x = 0;
  if (c == '-')
    second = -1, c = getChar();
  else if (c == '+')
    c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  return second == 1 ? x : -x;
}
inline double readDouble() {
  int second = 1, c = readChar();
  double x = 0;
  if (c == '-') second = -1, c = getChar();
  while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
  if (c == '.') {
    c = getChar();
    double coef = 1;
    while ('0' <= c && c <= '9') x += (c - '0') * (coef *= 1e-1), c = getChar();
  }
  return second == 1 ? x : -x;
}
inline void readWord(char *second) {
  int c = readChar();
  while (c > 32) *second++ = c, c = getChar();
  *second = 0;
}
inline bool readLine(char *second) {
  int c = getChar();
  while (c != '\n' && c != -1) *second++ = c, c = getChar();
  *second = 0;
  return c != -1;
}
static int write_buf_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x) {
  if (write_buf_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0;
  write_buf[write_buf_pos++] = x;
}
inline void flush() {
  if (write_buf_pos)
    fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0;
}
template <class T>
inline void writeInt(T x, char end, int output_len) {
  if (x < 0) writeChar('-'), x = -x;
  char second[24];
  int n = 0;
  while (x || !n) second[n++] = '0' + x % 10, x /= 10;
  while (n < output_len) second[n++] = '0';
  while (n--) writeChar(second[n]);
  if (end) writeChar(end);
}
inline void writeWord(const char *second) {
  while (*second) writeChar(*second++);
}
inline void writeDouble(double x, int output_len) {
  if (x < 0) writeChar('-'), x = -x;
  int t = (int)x;
  writeInt(t), x -= t;
  writeChar('.');
  for (int i = output_len - 1; i > 0; i--) {
    x *= 10;
    t = std::min(9, (int)x);
    writeChar('0' + t), x -= t;
  }
  x *= 10;
  t = std::min(9, (int)(x + 0.5));
  writeChar('0' + t);
}