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 problem, you are asked to implement a class Matrix that represents a \(N\times N\) matrix.

Given two matrix, \(A\) and \(B\) as follows:

\(\mathbf {A} ={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\\\end{pmatrix}},\quad \mathbf {B} ={\begin{pmatrix}b_{11}&b_{12}&\cdots &b_{1p}\\b_{21}&b_{22}&\cdots &b_{2p}\\\vdots &\vdots &\ddots &\vdots \\b_{n1}&b_{n2}&\cdots &b_{np}\\\end{pmatrix}}\)

The class should support the following operations:

1. add A = A + B → \(A = A+B\)
   \(A + B = {\begin{pmatrix}a_{11}+b_{11}&a_{12}+b_{12}&\cdots &a_{1n}+b_{1n}\\a_{21}+b_{21}&a_{22}+b_{22}&\cdots &a_{2n}+b_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}+b_{m1}&a_{m2}+b_{m2}&\cdots &a_{mn}+b_{mn}\\\end{pmatrix}}\)
2. subtract A = A - B → \(A = A-B\)
   \(A - B = {\begin{pmatrix}a_{11}-b_{11}&a_{12}-b_{12}&\cdots &a_{1n}-b_{1n}\\a_{21}-b_{21}&a_{22}-b_{22}&\cdots &a_{2n}-b_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}-b_{m1}&a_{m2}-b_{m2}&\cdots &a_{mn}-b_{mn}\\\end{pmatrix}}\)
3. multiply A = A * B → \(A = AB\)
   For \(C = AB\), \(C = {\begin{pmatrix}c_{11}&c_{12}&\cdots &c_{1p}\\c_{21}&c_{22}&\cdots &c_{2p}\\\vdots &\vdots &\ddots &\vdots \\c_{m1}&c_{m2}&\cdots &c_{mp}\\\end{pmatrix}},\ c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots +a_{in}b_{nj}=\sum _{k=1}^{n}a_{ik}b_{kj}\)
4. transpose A = !A → \(A = A^{\top}\)
   \(A^{\top} = {\begin{pmatrix}a_{11}&a_{21}&\cdots &a_{m1}\\a_{12}&a_{22}&\cdots &a_{m2}\\\vdots &\vdots &\ddots &\vdots \\a_{1n}&a_{2n}&\cdots &a_{mn}\\\end{pmatrix}}\)

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.

Constraints

$1 \leq N \leq 10$

$1 \leq T \leq 1000$

$o = {1,2,3,4}$

All numbers would not exceed the range of long long.

Subtask

1. (Testcases 1, 2) Only add, subtract.
2. (Testcases 3, 4) Only multiply.
3. (Testcases 5, 6) Only transpose.
4. (Testcases 7, 8) No additional constraints.

Output

Output the final result of the matrix.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14609.cpp

Partial Judge Header

14609.h

Tags

Discuss