ldq的女装

Time Limit: 15000 ms Memory Limit: 65536 KiB

Problem Description

ldq 最近做起了倒卖女装的生意。他时常会回收女装,也常有顾客上门咨询。

对于 ldq 回收到的每件女装,都有两种属性,美观度 b 和舒适度 c。

而每个上门咨询的顾客都有一个美观偏好值 x 和一个舒适偏好值 y,对于一件美观度为 b,舒适度为 c 的女装,他能获得的愉悦值可以表示为:b*x + c*y。

现在给你一系列回收/咨询的事件,对于每次咨询事件,你需要帮助 ldq 找到在当前的所有女装中,该顾客能获得的最大愉悦值是多少。

Input

输入数据有多组(数据组数不超过 20),到 EOF 结束。

对于每组数据:

  • 第一行输入一个整数 n (1 <= n <= 10^5),表示事件个数
  • 接下来输入 n 行,每行输入三个用空格隔开的整数来表示一个事件,事件种类如下:
    • 1 b c (1 <= b, c <= 10^4)。表示 ldq 回收了一件美观度为 b,舒适度为 c 的女装
    • 2 x y (1 <= x, y <= 10^4)。表示有一个美观偏好值为 x,舒适偏好值为 y 的顾客要询问当前他能获得的最大愉悦值是多少

Output

对于每组数据中的每次类型为 2 的事件,在一行中输出一个整数,表示当前所有女装中能获得的最大愉悦值。

Sample Input

7
2 1 1
1 4 2
1 2 3
2 4 1
2 2 5
1 3 6
2 2 5

Sample Output

0
18
19
36

Hint

对于第一次询问(2 1 1),当前 ldq 手中没有任何女装,最大愉悦值为 0。

对于第二次询问(2 4 1),当前女装有 {4, 2} 和 {2, 3},选择第一件女装愉悦值最大,最大愉悦值为 4*4 + 2*1 = 18。

对于第三次询问(2 2 5),当前女装有 {4, 2} 和 {2, 3},选择第二件女装愉悦值最大,最大愉悦值为 2*2 + 3*5 = 19。

对于第四次询问(2 2 5),当前女装有 {4, 2}、 {2, 3} 和 {3, 6},选择第三件女装愉悦值最大,最大愉悦值为 3*2 + 6*5 = 36。

Source

bLue