50130. Bank Accounts

I'm a slow walker, but I never walk backwards.

Task Description

We will implement an accounting program for multiple users. At the beginning, every user must register how much money he/she has by the instruction user balance. For example, the instruction Alice 1100 sets the balance of Alice to 1100. We assume that no users have the same name, and the name is a string that can be read for the "%s" format.

The program processes four basic banking instructions: $earns$, $spends$, $gives$, and $becomes$.

  • The instruction user earns amount increases the balance of $user$ by $amount$.
  • The instruction user spends amount decreases the balance of $user$ by $amount$.
  • The instruction user1 gives user2 amount transfers $amount$ from $user1$ to $user2$.
  • The instruction user becomes amount sets the balance of $user$ to $amount$.

Here is an example that how instructions work. The second and the third columns are the balance of Alice and Bob after processing the instruction in the first column.

Instruction Alice Bob
Alice 1100 1100
Bob 500 1100 500
Alice earns 300 1400 500
Bob spends 400 1400 100
Alice gives Bob 600 800 700
Alice becomes 1108 1108 700

To make the accounting process secret, the instructions may be $encrypted$. An instruction is encrypted by adding letters before/after the instruction. For example, the instruction gives may be encrypted as aaagivesbbb, or aaagives.

Here is an example that show how instructions are encrypted.

Instruction Alice Bob
Alice 1100 1100
Bob 500 1100 500
Alice learns 300 1400 500
Bob suspends 400 1400 100
Alice forgives Bob 600 800 700
Alice bebecomesout 1108 1108 700

Note that an instruction may be $invalid$. First, the instruction may involve $unregistered$ users. Recall that every user must register his/her balance at the beginning. Also the instruction itself may be $invalid$ because it cannot be decrypted into any valid instruction. For example, abc is not a valid instruction. Finally the instruction may be $invalid$ because the user does $not$ have enough money to spend or to give to the other user. Your program should $ignore$ every invalid instruction.

Here is an example that contains invalid instructions.

Instruction Alice Bob
Alice 1100 1100
Bob 500 1100 500
Trudy learns 300 1100 500
Bob suspends 800 1100 500
Alice borrows Bob 600 1100 500
Alice bebecomesout 124 124 500

Input Format

The input contains only one test case. The first line contains $N$, the number of users. Each of the following $N$ lines contains a string $S$ and an integer $M$. $S$ is the user’s name and $M$ is the balance. Each of the remaining lines is an instruction and you need to process all instructions until EOF.

  • $0 \lt N \lt 32$
  • The length of every part of an instruction, including user names, operation, and amount, is less than 32.
  • All amounts in the input are positive.

Output Format

There are $N$ lines in the output. The $i$-th line has the $i$-th user’s name (in the input order) and his/her balance after we process all instructions.

Subtasks

  • 30 points: Instructions are all valid and they are not encrypted.
  • 30 points: Instructions are all valid but may be encrypted.
  • 40 points: There may be invalid instructions.

Hints

We can put the user names in an array of strings userName, and the balance in another array of integer balance, so that balance[i] is the balance of the user whose name is in userName[i]. That is, when we are given a name, we should find the index i such that userName[i] matches the given name, then we can process his/her balance in balance[i].

Sample Input 1

2
Alice 1100
Bob 500
Alice earns 300
Bob spends 400
Alice gives Bob 600
Alice becomes 1108

Sample Output 1

Alice 1108
Bob 700

Sample Input 2

2
Alice 1100
Bob 500
Alice learns 300
Bob suspends 400
Alice forgives Bob 600
Alice bebecomesout 1108

Sample Output 2

Alice 1108
Bob 700

Sample Input 3

2
Alice 1100
Bob 500
Trudy earns 300
Bob suspends 800
Alice borrows Bob 600
Alice bebecomesout 124

Sample Output 3

Alice 124
Bob 500

Discussion