Description

Notice: Please use C++11 or above to submit this problem!

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 someone enter the casino, they have to pay T entrance fee to the casino. The enterance fee may change every day.

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. In particular, when someone blacklisted wants to enter the casino, they won't be charged the enterance fee.

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 T — it means there will be Q events and the entrance fee is T 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

13182.cpp

Partial Judge Header

13182.h

Tags

Discuss

Description

Kuo-chan is given a sequence A and a constant K as his birthday present from Yang-chan.

Kuo-chan is allowed to perfrom the following operation:

1. push x — push x to the tail of A
2. pop — remove the median value of A （the median value of A is A[ (|A|+1)/2 ], with index start at 1）
3. programming tanoshi — for every element a in A, assign a % K to a
4. reverse — reverse the whole A, the head becomes the tail and the tail becomes the head

 

Whenever performing pop operation, the length of A is guaranteed to be odd, hence A won't be empty.

 

For example, if A = [4, 3, 5], K = 2

push 11　►　A = [4, 3, 5, 11]

reverse ► A = [11, 5, 3, 4]

push 7　►　A = [11, 5, 3, 4, 7]

pop　►　A = [11, 5, 4, 7]

programming tanoshi　►　A = [1, 1, 0, 1] 

 

Yang-chan is curious about what A is after Kuo-chan performs some operations to it.

Help him find it out!

 

（Remember to include function.h in your function.cpp file.）

 

Input

The first line contains three integers N K Q — the length of A, the constant Yang-chan gives Kuo-chan, the number of operations Kuo-chan performs.

The second line contains N integers a₁, a₂, ..., a_N （1 <= a_i <= N） — the elements of A. 

Each of the next Q lines describes the operations. Each line is one of three types:

1. push x （1 <= x <= 10000）
2. pop
3. programming tanoshi
4. reverse

 

Different testcases have different constraints.

1. N <= 10³, Q <= 2N, K <= 4000, operations: {pop, push}
2. N <= 10³, Q <= 2N, K <= 4000, operations: {pop, push, programming tanoshi}
3. N <= 10⁵, Q <= 2N, K <= 4000, operations: {pop, push}
4. N <= 10⁵, Q <= 2N, K <= 4000, operations: {pop, push, programming tanoshi}
5. N <= 10⁵, Q <= 3N, K <= 4000, operations: {pop, push, programming tanoshi, reverse}
6. N <= 10⁵, Q <= 3N, K <= 4000, operations: {pop, push, programming tanoshi, reverse}

 

Output

You should print one line containing the elements of A after the operations. For 1 <= i <= |A|, the i-th number should be A[ i ].

Sample Input  Download

Sample Output  Download

Partial Judge Code

13472.cpp

Partial Judge Header

13472.h

Tags

Discuss

Description

In this problem, you are asked to implement a class Vector that represents a vector in 2D space. The class should support the following operations:

• Addition (+)
• Dot product (*)
• Cross product (^)

Using these operations, you should also be able to calculate the following:

• The area of the triangle formed by two vectors
• The projection of vector \(v_1\) onto vector \(v_2\)

useful link

Warning: You should use C++11 or later versions, or else you will get Compile Error! reason

Hint: Please use std::abs or fabs instead of abs to get the absolute value.

Input

The first line contains two integers \(x_1, y_1\), which represents the first vector \(v_1\).
The second line contains two integers \(x_2, y_2\), which represents the second vector \(v_2\).

\(x_1 \quad y_1\)
\(x_2 \quad y_2\)

Constraints

• \(1 \le x_1,y_1,x_2,y_2 \le 1000\)

Output

As main function in "14274.cpp"

Sample Input  Download

Sample Output  Download

Partial Judge Code

14274.cpp

Partial Judge Header

14274.h

Tags

Discuss

Description

In this problem, you are asked to implement a class Matrix that represents a $N\times N$ Matrix.

Following are the methods you should implement:

1. add A.add(B) → $A = A+B$
2. subtract A.subtract(B) → $A = A-B$
3. multiply A.multiply(B) → $A = AB$
4. transpose A.transpose() → $A = A^{\top}$
5. power A.power(x) → $\underbrace{AA \dots AA}_{\times x}$

Usefull links

Power of matrix:

Reference

Input

The first line contains two integers $N$, $T$, representing the size of the matrix and the number of the operations.

Following are $N$ lines, each line contains $N$ integers, representing the element in the starting matrix.

Following are $T$ operations, each operation start with an interger $o$, representings the type of the operation.

For operation type 1, 2, 3, interger $o$ is followed by $N\times N$ numbers, representing the element in the operand matrix.

For operation type 5, interger $o$ is followed by an interger $x$, repersentings $x$-th power.

Constraints

• $1 \leq N \leq 10$
• $1 \leq T \leq 1000$
• $o = {1,2,3,4,5}$
• $1 \leq x \leq 1e6$
• All numbers would not exceed the range of long long.

Subtask

1. (Testcases 1-6) $o = {1,2,3,4}$
2. (Testcases 7-8) $1 \leq x \leq 5$
3. (Testcases 9-10) No additional constraints.

Output

Output the final result of the matrix.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14605.cpp

Partial Judge Header

14605.h

Tags

Discuss