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>
using namespace std;
class SegTree {
 public:
  vector<long long> mat;
  vector<bool> has_data;
  vector<long long> lazy;
  long long max_res;
  int sz;
  SegTree(int len) {
    max_res = 6000000000000000000ll;
    int n = len * 4;
    mat = vector<long long>(n, max_res);
    lazy = vector<long long>(n, 0);
    has_data = vector<bool>(n, false);
    sz = n;
  }
  long long bulk_add(int idx, int stpnt, int endpnt, int target_start,
                     int target_end, long long val) {
    if (stpnt > endpnt) return max_res;
    if (stpnt == endpnt) {
      if (has_data[idx] == false) return max_res;
      if (stpnt > target_end || endpnt < target_start) {
        return mat[idx];
      }
      mat[idx] += val;
      lazy[idx] = 0;
      return mat[idx];
    }
    push_down(idx);
    if (has_data[idx] == false) return max_res;
    if (stpnt > target_end || endpnt < target_start) {
      if (has_data[idx] == false) {
        return max_res;
      }
      return mat[idx];
    }
    if (stpnt >= target_start && endpnt <= target_end) {
      mat[idx] += val;
      lazy[idx] += val;
      return mat[idx];
    }
    int mid = (stpnt + endpnt) / 2;
    return mat[idx] = min(
               bulk_add(idx * 2 + 1, stpnt, mid, target_start, target_end, val),
               bulk_add(idx * 2 + 2, mid + 1, endpnt, target_start, target_end,
                        val));
  }
  long long query_range(int idx, int stpnt, int endpnt, int target_start,
                        int target_end) {
    if (stpnt > endpnt) return max_res;
    if (stpnt == endpnt) {
      if (has_data[idx] == false || stpnt > target_end || endpnt < target_start)
        return max_res;
      return mat[idx];
    }
    push_down(idx);
    if (has_data[idx] == false) return max_res;
    if (stpnt > target_end || endpnt < target_start) return max_res;
    if (stpnt >= target_start && endpnt <= target_end) {
      return mat[idx];
    }
    int mid = (stpnt + endpnt) / 2;
    long long left =
        query_range(idx * 2 + 1, stpnt, mid, target_start, target_end);
    long long right =
        query_range(idx * 2 + 2, mid + 1, endpnt, target_start, target_end);
    long long res = min(left, right);
    return res;
  }
  pair<long long, bool> insert_val(int idx, int stpnt, int endpnt, int target,
                                   long long val) {
    if (stpnt > endpnt) return make_pair(max_res, false);
    if (stpnt == endpnt) {
      if (stpnt > target || endpnt < target) {
        if (has_data[idx] == false) return make_pair(max_res, has_data[idx]);
        return make_pair(mat[idx], has_data[idx]);
      }
      mat[idx] = val;
      has_data[idx] = true;
      lazy[idx] = 0;
      return make_pair(val, true);
    }
    push_down(idx);
    if (stpnt > target || endpnt < target) {
      if (has_data[idx] == false) {
        return make_pair(max_res, false);
      }
      return make_pair(mat[idx], has_data[idx]);
    }
    int mid = (stpnt + endpnt) / 2;
    pair<long long, bool> left =
        insert_val(idx * 2 + 1, stpnt, mid, target, val);
    pair<long long, bool> right =
        insert_val(idx * 2 + 2, mid + 1, endpnt, target, val);
    mat[idx] = min(left.first, right.first);
    has_data[idx] = (left.second || right.second);
    return make_pair(mat[idx], has_data[idx]);
  }
  pair<long long, bool> delete_val(int idx, int stpnt, int endpnt, int target) {
    if (stpnt > endpnt) return make_pair(max_res, false);
    if (stpnt == endpnt) {
      if (stpnt > target || endpnt < target) {
        if (has_data[idx] == false) return make_pair(max_res, false);
        return make_pair(mat[idx], has_data[idx]);
      }
      mat[idx] = max_res;
      has_data[idx] = false;
      lazy[idx] = 0;
      return make_pair(max_res, false);
    }
    push_down(idx);
    if (stpnt > target || endpnt < target) {
      if (has_data[idx] == false) {
        return make_pair(max_res, false);
      }
      return make_pair(mat[idx], has_data[idx]);
    }
    int mid = (stpnt + endpnt) / 2;
    pair<long long, bool> left = delete_val(idx * 2 + 1, stpnt, mid, target);
    pair<long long, bool> right =
        delete_val(idx * 2 + 2, mid + 1, endpnt, target);
    mat[idx] = min(left.first, right.first);
    has_data[idx] = (left.second || right.second);
    if (has_data[idx] == false) {
      mat[idx] = max_res;
    }
    return make_pair(mat[idx], has_data[idx]);
  }
  void push_down(int idx) {
    if (has_data[idx] == false) {
      mat[idx] = max_res;
      lazy[idx] = 0;
      return;
    }
    int left_idx = idx * 2 + 1;
    int right_idx = idx * 2 + 2;
    if (has_data[left_idx]) {
      mat[left_idx] += lazy[idx];
      lazy[left_idx] += lazy[idx];
    }
    if (has_data[right_idx]) {
      mat[right_idx] += lazy[idx];
      lazy[right_idx] += lazy[idx];
    }
    lazy[idx] = 0;
  }
};
void test_seg_tree() {
  SegTree s(3);
  long long val_0, val_1, val_2;
  s.insert_val(0, 0, 2, 0, 0);
  cout << "starting:" << endl;
  val_0 = s.query_range(0, 0, 2, 0, 0);
  cout << "val_0: " << val_0 << endl;
  s.insert_val(0, 0, 2, 1, 2);
  cout << "starting:" << endl;
  val_0 = s.query_range(0, 0, 2, 0, 0);
  cout << "starting:" << endl;
  val_1 = s.query_range(0, 0, 2, 1, 1);
  cout << "val_0: " << val_0 << " val_1: " << val_1 << endl;
  s.insert_val(0, 0, 2, 2, 3);
  cout << "starting:" << endl;
  val_0 = s.query_range(0, 0, 2, 0, 0);
  cout << "starting:" << endl;
  val_1 = s.query_range(0, 0, 2, 1, 1);
  cout << "starting:" << endl;
  val_2 = s.query_range(0, 0, 2, 2, 2);
  cout << "val_0: " << val_0 << " val_1: " << val_1 << " val_2: " << val_2
       << endl;
}
int main() {
  int q;
  scanf("%d", &q);
  vector<vector<long long> > inp(q, vector<long long>(4, 0));
  set<long long> all_t;
  set<long long> cur_t;
  map<long long, int> t_idx;
  map<int, long long> idx_to_t;
  map<long long, long long> t_s;
  for (int i = 0; i < q; i++) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      long long t, s;
      scanf("%lld %lld", &t, &s);
      inp[i][0] = type;
      inp[i][1] = t;
      inp[i][2] = s;
      all_t.insert(t);
    } else if (type == 2) {
      long long t;
      scanf("%lld", &t);
      inp[i][0] = type;
      inp[i][1] = t;
    } else {
      long long l, r, v;
      scanf("%lld %lld %lld", &l, &r, &v);
      inp[i][0] = type;
      inp[i][1] = l;
      inp[i][2] = r;
      inp[i][3] = v;
    }
  }
  SegTree tree((int)all_t.size());
  int max_t_len = (int)all_t.size();
  int cnt = 0;
  for (set<long long>::iterator it = all_t.begin(); it != all_t.end(); it++) {
    t_idx[*it] = cnt;
    idx_to_t[cnt] = *it;
    cnt++;
  }
  for (int i = 0; i < inp.size(); i++) {
    if (inp[i][0] == 1) {
      long long t, s;
      t = inp[i][1];
      s = inp[i][2];
      int cur_t_idx = t_idx[t];
      set<long long>::iterator it = cur_t.upper_bound(t);
      long long prev_val = 0;
      long long prev_s = 0;
      long long prev_t = 0;
      if (it != cur_t.begin()) {
        set<long long>::iterator it2 = it;
        it2--;
        prev_t = *it2;
        prev_s = t_s[prev_t];
        int idx = t_idx[prev_t];
        prev_val = tree.query_range(0, 0, max_t_len - 1, idx, idx);
      }
      long long val_to_insert = prev_val + (t - prev_t) * prev_s;
      tree.insert_val(0, 0, max_t_len - 1, cur_t_idx, val_to_insert);
      if (it != cur_t.end()) {
        long long next_t = *it;
        int idx = t_idx[next_t];
        long long next_val = tree.query_range(0, 0, max_t_len - 1, idx, idx);
        long long updated_val = val_to_insert + (next_t - t) * s;
        long long diff = updated_val - next_val;
        tree.bulk_add(0, 0, max_t_len - 1, idx, max_t_len - 1, diff);
      }
      cur_t.insert(t);
      t_s[t] = s;
    } else if (inp[i][0] == 2) {
      long long t;
      t = inp[i][1];
      int cur_t_idx = t_idx[t];
      set<long long>::iterator it = cur_t.upper_bound(t);
      long long prev_val = 0;
      long long prev_s = 0;
      long long prev_t = 0;
      if (it != cur_t.begin()) {
        set<long long>::iterator it2 = it;
        it2--;
        if (it2 != cur_t.begin()) {
          it2--;
          prev_t = *it2;
          prev_s = t_s[prev_t];
          int idx = t_idx[prev_t];
          prev_val = tree.query_range(0, 0, max_t_len - 1, idx, idx);
        }
      }
      tree.delete_val(0, 0, max_t_len - 1, cur_t_idx);
      if (it != cur_t.end()) {
        long long next_t = *it;
        int idx = t_idx[next_t];
        long long next_val = tree.query_range(0, 0, max_t_len - 1, idx, idx);
        long long updated_val = prev_val + (next_t - prev_t) * prev_s;
        long long diff = updated_val - next_val;
        tree.bulk_add(0, 0, max_t_len - 1, idx, max_t_len - 1, diff);
      }
      cur_t.erase(t);
    } else {
      double res = -1;
      long long l, r, v;
      l = inp[i][1];
      r = inp[i][2];
      v = inp[i][3];
      set<long long>::iterator it = cur_t.lower_bound(l);
      if (v <= 0) {
        res = l;
      } else if (it != cur_t.end() && (*it) < r) {
        long long start_t = *it;
        int start_idx = t_idx[start_t];
        long long start_val =
            tree.query_range(0, 0, max_t_len - 1, start_idx, start_idx);
        long long target_val = start_val - v;
        set<long long>::iterator it2 = cur_t.upper_bound(r);
        it2--;
        long long end_t = *it2;
        long long end_s = t_s[end_t];
        int end_idx = t_idx[end_t];
        long long end_val =
            tree.query_range(0, 0, max_t_len - 1, end_idx, end_idx);
        int start = start_idx;
        int end = end_idx;
        long long foud_min = tree.max_res;
        while (start < end) {
          foud_min = tree.query_range(0, 0, max_t_len - 1, start, end);
          if (foud_min > target_val) {
            start = end;
            break;
          }
          int mid = (start + end) / 2;
          long long min_val = tree.query_range(0, 0, max_t_len - 1, start, mid);
          if (min_val > target_val) {
            start = mid + 1;
          } else {
            foud_min = min_val;
            end = mid;
          }
        }
        if (foud_min <= target_val) {
          long long t = idx_to_t[start];
          set<long long>::iterator it3 = cur_t.lower_bound(t);
          it3--;
          long long prev_t = *it3;
          long long prev_s = t_s[prev_t];
          int prev_idx = t_idx[prev_t];
          long long prev_val =
              tree.query_range(0, 0, max_t_len - 1, prev_idx, prev_idx);
          res = (double)prev_t +
                ((double)target_val - (double)prev_val) / (double)prev_s;
        } else {
          long long last_val = end_val + (r - end_t) * end_s;
          if (last_val <= target_val) {
            res = (double)end_t +
                  ((double)target_val - (double)end_val) / (double)end_s;
          }
        }
      }
      if (res < 0) {
        printf("%lf\n", res);
      } else {
        printf("%.10lf\n", res);
      }
    }
  }
  return 0;
}