Description

After watching the movie 21, Kuo is curious about casino.

 

There is a casino which opens N days in this month.

There will be two kind of events in a day.

1. Guest <Someone> <Money> <Skill>. It means <Someone> enter the casino with <Money> money. <Someone> are their names, <Money> is the amount of money with them, and <Skill> is how well they play. If <Someone> are already in the casino or are blacklisted, ignore this event.
2. Win <Someone> <Money>. It means <Someone> win <Money> money in a play from the casino. <Money> may be positive or negative. If <Someone> are not in the casino or are blacklisted, ignore this event.

 

Whenever one become bankrupt, they will be kicked out of the casino and be blacklisted.

If the amout of money someone win in a play exceed (that is, >) twice of their <Skill>, they will be seen as cheaters, kicked out of the casino, and blacklisted. (The casino still has to pay the money they win to them.)

Someone blacklisted are not permitted to enter the casino.

Note: If someone have to pay X money but they only have Y money where Y <= X, they will only pay Y money and become bankrupt.

At the end of each day, everyone will leave the casino.

 

Please help Kuo-chan find how much income the casino gets in this month and who are blacklisted.

Input

The first line of the input contains a number N — the number of days in this month.

The following contains N blocks.

The first line of each block is Casino Q — it means there will be Q events this day.

The next Q lines is one of the following:

1. Guest <Someone> <Money> <Skill>
2. Win <Someone> <Money>

 

N <= 1000, Q <= 100. 

There will be at most 1000 different people come to the casino; that is, there are at most 1000 people with different names. Therefore, there will be at most 1000 people blacklisted.

All number is within the range of int.

Output

You should print a number U in the first line — how much income the casino gets in this month.

If there are K people blacklisted in this month, you should output their names in K lines in the order they get blacklisted.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13184.cpp

Partial Judge Header

13184.h

Tags

Discuss

Description

In this partial-judged problem, you are to implement a class polynomial which supports the following basic operation:

• Read coefficients from an istream (for instance, cin is an object of istream)
• Write the polynomial in a readable format to an ostream (for instance, cout is an object of ostream)
• Add two polynomials
• Subtract two polynomials

A polynomial has two properties: an integer degree and an array coefficients. For the purpose of simplify the constructor and destructor, we use std::array<> which appeared since C++11 rather than the conventional C-style array. You can use it as is.

Due to it is a bit tricky to overload the operator>> with istream, it had been almost done for you and you only need to implement a method to complete the operator.

Check function.h cautiously before you start.

Input

There are several testcases, each of which contains two lines of polynomials \(A(x), B(x)\) and a black line. For each line of polynomial, it is started by an interger \(d\) indicating the degree of the polynomial, followed by \(d+1\) intergers which are the coeffcients in the descending order.

The degree won't exceed \(10^5\). (It's defined as N in function.h.)

It's guranteed that the polynomial is valid, i.e., the leading coefficient is not zero.

For 20% of testcases, the coefficients of \(A(x), B(x), A(x)-B(x)\) are positive.

For 50% of testcases, the coefficients of \(A(x), B(x)\) are positive and the coefficient of \(A(x)-B(x)\) are non-negative.

Output

For every two polynomial, the main() would print out \(A(x), B(x), A(x)+B(x), A(x)-B(x)\) and a blank line.

The output format of the polynomial is:

• A polynomial consists of several terms. Print them in descending order.
• A term has 3 properties: sign, coefficient (so it is always positive) and exponent.
  • For the sign:
    • If it is leading term, then print the minus sign when the leading coefficient is negative, else not print any if it is positive.
    • Otherwise print the sign with spaces around it. (" + " or " - " without the quotation marks)
  • For the coefficient \(c\), print \(c\) if \(c\ne1\) or it is a constant term.
  • For the exponent \(e\), print x^\(e\) if \(e>1\), else print x if \(e=1\), otherwise not print any if it is a constant term.
• Only term whose coefficient is not zero should be printed, except that the polynomial is a zero polynomial, i.e. degree is zero and constant term is also zero.

The sample output includes many examples.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13481.cpp

Partial Judge Header

13481.h

Tags

Discuss