Fedya 和 Sasha 是朋友,这就是为什么 Sasha 了解 Fedya 的一切。
Fedya 将耐心放在一个无限大的碗里。但是,与碗不同,Fedya 的耐心不是无限的,这就是为什么让 $$$v$$$ 为 Fedya 耐心的升数,并且,一旦 $$$v$$$ 等于 $$$0$$$,碗就会立即破裂。碗里有一个水龙头,每秒可以泵出 $$$s$$$ 升的耐心。请注意,$$$s$$$ 可能为负数,在这种情况下,水龙头会耗尽耐心。萨沙可以做不同的事情,因此他能够改变水龙头的速度。 Sasha 执行的所有操作都可以表示为 $$$q$$$ 查询。查询分为三种类型:
1. "1 t s" — 添加一个新事件,意味着从第 $$$t$$$ 秒开始,点击速度将等于 $$$s$$$。
2. "2 t" — 删除第 $$$t$$$ 秒发生的事件。保证这种事件存在。
3.“3 l r v”——Sasha 想知道:如果你采取 $$$l \le t \le r$$$ 的所有事件,并模拟从第 $$$l$$$ 秒开始到第 $$$r$$$ 秒开始(包括第 $$$l$$$ 秒开始时的初始耐心量),Fedya 耐心的变化$$$v$$$升)那么什么时候碗就会爆裂。如果这种情况没有发生,那么答案将是 $$$-1$$$。
由于 Sasha 不想检查 Fedya 的耐心结束后会发生什么,并且他已经提出了查询,因此他要求您帮助他并找到 $$$3$$$-rd 类型的每个查询的答案。
保证在任何时刻,不会有两个事件同时发生。
输入
第一行包含一个整数 $$$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$$$-rd类型的查询,并且不会有$$$1$$$-st类型的查询与$$$t$$$,即已经存在在第二个$$$t$$$发生的事件。
输出
对于 $$$3$$$-rd 类型的每个查询,在一个新行中打印碗将爆裂的时刻,或者如果不会发生则打印 $$$-1$$$。
如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$ 时,您的答案才会被接受。
示例
输入 #1
6 1 2 1 1 4 -3 3 1 6 1 3 1 6 3 3 1 6 4 3 1 6 5
输出 #1
5 5.666667 6 -1
输入 #2
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
输出 #2
-1 5 8.7 8.1 -1
输入 #3
5 1 1000 9999999 1 2000 -9999 3 1000 2000 0 2 1000 3 1000 2002 1
输出 #3
1000 2000.0001
注意
在第一个示例中,$$$3$$$-rd 类型的所有查询涵盖了所有事件,其模拟如下: