Financial Advisor Profit Estimation

Blue Mary receives proposals from various financial advisors. Each financial advisor i designs a profit scheme such that the profit on each day is strictly higher than the previous day and increases by a constant amount \(P_i\). In other words, if the first day profit is \(a_i\), then the profit on day \(d\) is \(a_i+(d-1)\,P_i\).

Blue Mary estimates the profit on a particular day by simply choosing, among all the proposals received so far, the one that gives the highest profit on that day. If no proposal has been received yet, the profit for any day is regarded as 0.

You are to process a series of operations. There are two types of operations:

• Proposal Operation: Denoted by a line starting with P followed by two numbers \(a\) and \(p\). It represents that a financial advisor submits a profit scheme with first day profit \(a\) and daily increment \(p\). Thus, on day \(d\), the profit is \(a+(d-1)\,p\).
• Query Operation: Denoted by a line starting with Q followed by an integer \(d\). For this operation, you need to output the maximum profit on day \(d\) among all proposals received so far. If no proposal exists, output 0.

Input Example:

3
Q 2
P 0 1
Q 2

For the above input, the output should be:

0
1

Another example:

5
Q 2
P 0 1
Q 2
P 2 0.1
Q 2

The expected outputs for the queries are 0, 1, and 2.1 respectively.

inputFormat

The first line contains an integer \(n\) representing the number of operations. The following \(n\) lines each describe an operation. An operation is either:

• P a p - A proposal operation where \(a\) (a float) is the first day profit and \(p\) (a float) is the daily increment.
• Q d - A query operation where \(d\) (an integer) is the day for which you must output the maximum profit among all proposals received so far.

If there are no proposals when a query is made, consider the profit for that day to be 0.

outputFormat

For each query operation, output a line containing a single number — the maximum profit on that day according to the proposals received so far. For floating point results, it is acceptable to output in standard decimal notation.

sample

3
Q 2
P 0 1
Q 2

0
1

</p>