T284656 改试卷（paper）

zyc快速地浏览了一下手上的数学试卷，并且拿向下一张。 “咦……是他的。唉，他怎么这个时候总是不在。”他叹道。“这下得好好改了。” “这是什么做法啊……这么复杂？这到底是不是对的啊？” 他手上的试卷采用了一种极度复杂的暴算方法，并跳过了所有计算过程，只有若干个“解得”“可推得”。

为了检查这个做法是否正确，他不得不维护一个初始为空的二维点集，并支持以下操作共 $n$ 次： 1. 向集合内加入一个点 $(x,y)$。 2. 从集合内删除第 $x$ 次操作加入的点。保证第 $x$ 次操作是 1 操作。 3. 给出参数 $a,b$，询问对于当前点集内的所有点 $(x,y)$，$ax+by$ 的最大值是多少。特别的，若当前点集为空，规定答案为0。 zyc发现暴力检查的话就会像手上这张卷子的主人一样浪费整整一小时的时间才能算完。 所以，他想找到更好的方法。 不过，他总喜欢再检查一遍。所以，请你看看他和你算的结果是不是一样的吧。

第一行一个整数 $n$，表示操作次数。 接下来 $n$ 行，每行为 `1 x y` 或 `2 x` 或 `3 x y` ，表示题面中给出的一种操作。

对于每个 3 操作，输出对应的答案，单独占一行。

对于前 $20\%$ 的数据，$n\le 2000$。 对于前 $40\%$ 的数据，$n\le 5\times 10^4$。 对于前 $70\%$ 的数据，$n\le 10^5$。 对于所有数据，$1\le n\le 10^6,0\le x,y,a,b\le 10^9$。 保证操作2给出的 必定能对应上一个操作1。