题目描述

Blue Mary 经营公司，金融顾问们提供收益方案。每个方案中，第 $t$ 天的收益为：

其中 $S$ 是第一天的收益，$P$ 是每天的增长量。

Blue Mary 每天选择所有方案中当天收益最大的方案，并累加得到总收益。需要支持两种操作：

• Project：添加一个方案 $(S, P)$
• Query T：查询第 $T$ 天按上述方法选择的最大收益

输入格式

第一行：整数 $N$（操作总数）

接下来 $N$ 行：

• Query T：查询第 $T$ 天的最大收益
• Project S P：添加方案，首日收益 $S$，日增长 $P$

输出格式

对每个 Query 输出一个整数，表示该天最大收益（精确到整百元，如 $210$ 或 $290$ 均输出 $2$）

样例

输入

10
Project 5.10200 0.65000
Project 2.76200 1.43000
Query 4
Query 2
Project 3.80200 1.17000
Query 2
Query 3
Query 1
Project 4.58200 0.91000
Project 5.36200 0.39000

输出

0
0
0
0
0

数据范围与提示

• $1 \leq N \leq 10^5$
• $1 \leq T \leq 50000$
• $0 < P < 100$
• $|S| \leq 10^5$