题目描述

在一起将 $a$ 城的蛋糕店都吃过一遍后，你和唐芯都各自选出了自己最心仪的蛋糕店——“兰璱辰” 店与 “澄璱辰” 店，下简记为 $L$ 店与 $C$ 店。作为甜品的狂热爱好者，唐芯每周都会去 $C$ 店买她心爱的草莓蛋糕来吃，不过，“两个总比一个好”，所以她总是帮你去 $L$ 店也买一份，再 “顺便帮你吃一点儿”。

对于每个草莓蛋糕都有两个值 $c, y$ ，分别代表蛋糕的卡路里和美味度，奇怪的是，美味度越小代表蛋糕越美味。同时，两家蛋糕店里卖的草莓蛋糕可以分别被表示成 多重集 $L, C$ ** 。 蛋糕店里卖的草莓蛋糕不会是一成不变的。具体地，在唐芯相邻两次买蛋糕的时间间隔中， $L$ 店与 $C$ 店中会有一家店进行一个草莓蛋糕的上新或下架。另外需要强调的是，唐芯购买蛋糕并不会造成**多重集 $L$ ， $C$ 的变化。

由于唐芯会 “吃一点儿” 你的那份，所以对于一组买蛋糕方案 $a \in L, b \in C$ ，唐芯会增加的卡路里 是 $a_c + b_c$ ，感受到的美味度是 $a_y + b_y$ 。作为一名女演员，唐芯必须控制她的体重，但她同时也不想在享受美食的过程中太委屈自己。也就是说，定义 $\max\{a_c + b_c, a_y + b_y\}$ 为唐芯对一组买蛋糕方案的不喜爱度，她希望能找到一组买蛋糕方案，使得其不喜爱度最小。

由于唐芯马上要赶去《鲛人泪》剧组进行拍摄，所以她将接下来 $Q$ 周的买蛋糕任务交给了你。为 了方便起见，你只需要告诉她每周的最小不喜爱度即可。

输入格式

第一行包含一个整数 $Q$ ，含义如上所述。

接下来 $Q$ 行，每行包含四个整数 $opt, d, c, y$ ，其中 $opt = 0/1$ 分别表示下架/上新一个草莓蛋糕， $d = 0/1$ 分别表示 $L$ 店/ $C$ 店， $c, y$ 描述这个草莓蛋糕的卡路里与美味度。

输出格式

对于每个操作，你都需要输出操作后的最小不喜爱度的值。特别地，如果有一家蛋糕店没有草莓蛋糕，输出 $-1$ 。

数据范围

对于所有测试点： $1 \le Q \le 10^6，1 \le c, y \le 10^9$ 。

每个测试点的具体限制见下表：

特殊限制 $A$ ：不存在下架操作。

输入样例 1

6
1 0 5 10
1 1 100 23
1 1 1 45
1 1 22 33
1 0 2 3
0 1 22 33

输出样例 1

-1
105
55
43
36
48

输入样例 2

4
1 1 1000000000 1
1 0 2 1000000000
1 0 500 12345678
0 1 1000000000 1

输出样例 2

-1
1000000002
1000000002
-1

样例解释

对于样例 $1$ ，

第一周， $L = \{\{5, 10\}\}, C = \varnothing$ ，所以输出 $-1$ ； 第二周， $L = \{\{5, 10\}\}, C = \{\{100, 23\}\}$ ，此时买蛋糕方案是唯一的，所以输出 $max\{5 + 100, 10 + 23\} = 105$ ； 第三周， $L = \{\{5, 10\}\}, C = \{\{100, 23\}, \{1, 45\}\}$ ，此时选择 $a = \{5, 10\}, b = \{1, 45\}$ ，所以输出 $55$ ； 第四周， $L = \{\{5, 10\}\}, C = \{\{100, 23\}, \{1, 45\}, \{22, 33\}\}$ ，此时选择 $a = \{5, 10\}, b = \{22, 33\}$ ，所以输出 $43$ ； 第五周， $L = \{\{5, 10\}, \{2, 3\}\}, C = \{\{100, 23\}, \{1, 45\}, \{22, 33\}\}$ ，此时选择 $a = \{2, 3\}, b = \{22, 33\}$ ，所以输出 $36$ ； 第六周， $L = \{\{5, 10\}, \{2, 3\}\}, C = \{\{100, 23\}, \{1, 45\}\}$ ，此时选择 $a = \{2, 3\}, b = \{1, 45\}$ ，所以输出 $48$ 。