CF1109C.Sasha and a Patient Friend

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 \le t \le 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.

费迪亚和萨沙是朋友，因此萨沙对费迪亚的一切都了如指掌。

费迪亚将他的耐心储存在一个无限大的碗中。然而，与这个碗不同，费迪亚的耐心并非无限——设 $v$ 表示费迪亚当前耐心的容量（单位：升）；一旦 $v$ 变为 $0$，碗便会立即破裂。碗中装有一个水龙头，每秒向碗中注入（或抽出）$s$ 升耐心。注意：$s$ 可以为负数，此时水龙头将从碗中抽出耐心。萨沙可以执行各种操作，从而改变水龙头的流速。萨沙的所有操作可表示为 $q$ 个查询，共有以下三种类型：

1. “1 t s” —— 添加一个新事件，表示从第 $t$ 秒起，水龙头的流速变为 $s$。
2. “2 t” —— 删除发生在第 $t$ 秒的事件。题目保证该事件一定存在。
3. “3 l r v” —— 萨沙想知道：若仅考虑所有满足 $l \le t \le r$ 的事件，并模拟从第 $l$ 秒初到第 $r$ 秒初（含端点）这一时间段内费迪亚耐心的变化（在第 $l$ 秒初，耐心初始容量为 $v$ 升），那么碗将在何时破裂？若在整个过程中碗均未破裂，则答案为 $-1$。

由于萨沙并不想亲自验证费迪亚耐心耗尽时会发生什么，而他已预先设计好了全部查询，因此他请你帮忙，对每个第 $3$ 类查询给出答案。

题目保证：在任意时刻，不会存在两个发生在同一秒的事件。

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

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

• 1 t s ($1 \le t \le 10^9$, $-10^9 \le s \le 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 \le t \le 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 \le l \le r \le 10^9$, $0 \le v \le 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$.

第一行包含一个整数 $q$（$1 \le q \le 10^5$），表示查询次数。

接下来的 $q$ 行中，每行属于以下格式之一：

• 1 t s（$1 \le t \le 10^9$，$-10^9 \le s \le 10^9$）：表示添加一个新事件，即从第 $t$ 秒起，水龙头的流速变为 $s$。
• 2 t（$1 \le t \le 10^9$）：表示删除发生在第 $t$ 秒的事件。保证该事件一定存在。
• 3 l r v（$1 \le l \le r \le 10^9$，$0 \le v \le 10^9$）：表示你需要模拟从第 $l$ 秒初开始、至第 $r$ 秒初（含）为止的过程，并回答碗将在何时破裂。

保证所有查询中的 $t$、$s$、$l$、$r$、$v$ 均为整数。

此外，保证至少存在一个类型为 3 的查询，且不会出现类型为 1 的查询，其 $t$ 值与已存在的某个事件的发生时刻相同。

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|)}} \le 10^{-6}$.

对于每个第 3 类查询，请在新的一行中输出碗破裂的时刻；若碗永远不会破裂，则输出 $-1$。

当你的答案绝对误差或相对误差不超过 $10^{-6}$ 时，即视为正确。

形式化地，设你的答案为 $a$，评测组的答案为 $b$。当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$ 时，你的答案被接受。

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

在第一个例子中，所有第 $3$ 类查询均覆盖全部事件，其模拟过程如下：