克鲁斯卡尔博士（Doctor Kruskal）正在创办一项泰伯利亚（tiberium）贸易业务。他有 $N$ 个潜在的泰伯利亚供应商，以及许多有兴趣获取泰伯利亚以运行自己工业的客户。

日历天数按时间顺序用正整数编号，每个供应商由 $1$ 到 $N$ 之间的唯一整数标识。供应商 $i$ 可以从第 $S_i$ 天起（包含第 $S_i$ 天）的任何一天供应泰伯利亚，但不能在第 $S_i$ 天之前供应。他们收取的服务价格为每天 $P_i$ 美元。由于克鲁斯卡尔非常聪明，供应商列表中仅包含城市中最好的供应商。此外，对于 $i = 1, 2, \dots, N - 1$，满足 $S_i < S_{i+1}$ 且 $P_i > P_{i+1}$。

克鲁斯卡尔的系统维护着一个可用客户的数据库。最初，该数据库为空，不包含任何客户。客户将陆续到达，并在到达时立即被添加到数据库中。第 $j$ 个客户有兴趣在截止到第 $E_j$ 天（包含第 $E_j$ 天）的任何一天接收泰伯利亚。对于他们接收泰伯利亚的每一天，他们的工业将产生 $R_j$ 美元的每日总收入。因此，如果克鲁斯卡尔将供应商 $i$ 与客户 $j$ 进行匹配，在扣除泰伯利亚成本后，该项交易的最终利润将为 $(R_j - P_i) \times (E_j - S_i + 1)$，其中要求 $S_i \le E_j$，否则无法提供任何泰伯利亚。

在任何时刻，克鲁斯卡尔的系统都可以针对任意特定的供应商 $i$，快速计算出数据库中所有可用客户里的最优客户，使得该供应商与该客户匹配时的交易利润最大化，并报告该最大利润。如果对于某个供应商，与任何可用客户匹配都无法获得正利润，则系统报告利润为零。

请注意，当系统被要求计算某个给定供应商的最大利润时，该供应商最多与一个可用客户进行匹配，且这种匹配对未来的操作没有任何影响。这意味着该供应商和该客户都可以在未来的匹配中再次被考虑。

你的任务是实现克鲁斯卡尔的系统。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 2 \times 10^5$），表示供应商的数量。

接下来的 $N$ 行中，第 $i$ 行描述供应商 $i$，包含两个整数 $S_i$ 和 $P_i$（$1 \le S_i, P_i \le 10^9$），分别表示该供应商的起始天数和每日价格。保证对于 $i = 1, 2, \dots, N - 1$，有 $S_i < S_{i+1}$ 且 $P_i > P_{i+1}$。

下一行包含一个整数 $Q$（$1 \le Q \le 2 \times 10^5$），表示需要处理的操作数量。

接下来的 $Q$ 行按系统执行的顺序描述操作，每行一个操作。操作共有两种类型：

• 如果操作是向数据库中添加一个客户，则该行包含小写字母 c，后跟两个整数 $E$ 和 $R$（$1 \le E, R \le 10^9$），分别表示该客户的截止天数和每日总收入。
• 如果操作是请求计算某个供应商的最大利润，则该行包含小写字母 s，后跟一个整数 $I$（$1 \le I \le N$），表示该供应商的编号。保证输入中至少包含一个此类操作。

输出格式

对于每个类型为 s 的操作，输出一行。该行必须包含一个整数，表示将给定供应商与可用客户匹配时所能获得的最大可能利润。按照操作在输入中出现的顺序输出结果。

样例

输入样例 1

4
2 8
4 5
7 3
9 2
11
s 1
c 10 10
s 1
s 2
s 3
s 4
c 7 26
s 2
s 4
s 3
s 1

输出样例 1

0
18
35
28
16
84
16
28
108