Description

Starting is hard, and running a company is even harder. Initial profits are usually low, but they gradually improve over time. That is, for a financial consultant $i$, in the plan they design, each day's profit is higher than the previous day by the same amount $P_i$.

Because the consultants are not very efficient, at any particular time Blue Mary can only estimate the maximum profit for some day based on the plans she has already received. Since Blue Mary has little financial sense, when estimating the best profit for each day she does not consider the past at all, and simply chooses, among all consultants' plans, the profit of the plan that gives the largest profit on that day. For example:

Two consultants have designed profit plans for the first four days as follows:

On Day 1, Blue Mary believes the maximum profit is $2$ (using Consultant 2's plan), and on Days 3 and 4 she believes the maximum profits are $9$ and $13$, respectively (using Consultant 1's plan). She believes the total maximum profit for the first four days is $2 + 5 + 9 + 13 = 29$.

Now, as the deputy general manager of Blue Mary's company, you will occasionally receive consultants' plans and must also answer Blue Mary's queries for the "maximum profit" on some day (the "maximum profit" is computed according to Blue Mary's method). Initially, when no plan has been received, you may assume the maximum profit for every day is $0$. Here is an example of received plans and answered queries:

• Query $2$, answer $0$.
• Receive plan: $0\ 1\ 2\ 3\ 4\ 5\ \cdots$.
• Query $2$, answer $1$.
• Receive plan: $2\ 2.1\ 2.2\ 2.3\ 2.4\ \cdots$.
• Query $2$, answer $2.1$.

Input Format

The first line contains an integer $N$, the total number of plans and queries.

The next $N$ lines each begin with a word Query or Project.

If the word is Query, it is followed by an integer $T$, meaning Blue Mary asks for the maximum profit on Day $T$.

If the word is Project, it is followed by two real numbers $S, P$, meaning that in this plan the profit on Day 1 is $S$, and afterwards each day's profit is greater than the previous day's by $P$.

Output Format

For each Query, output one integer, reported in hundreds of yuan (i.e., in units of 100 yuan; for example, if the maximum profit on that day is $210$ or $290$, you should output $2$). When there is no plan, output $0$ for the query.

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

Hint

Constraints

$1 \leq N \leq 10^5$, $1 \leq T \leq 5 \times 10^4$, $0 < P < 100$, $|S| \leq 10^5$.

Hint

The amount of input and output may be quite large. Please use fast I/O methods.

Translated by ChatGPT 5