International Collegiate Programming Contest

Time limit1sMemory limit128 MB

Summary

Given the exact output of a banking simulator, rebuild the canonical input: map each result line to a fixed request and choose the smallest initial balance B that keeps every request valid.

Level: Hard8 of 10
Topics: Simulation, Implementation, Greedy, Math
Solved: No attempts yet

Problem

Do you have any idea how much work a contest like this takes? Reserving rooms, installing computers, buying food, printing certificates, and that is only part of the list. Since the first CTU contest in 1995 the organizers have spent a lot of sleepless nights, all so that people like you can enjoy the ICPC.

The problem set needs the most care of all. Writing the statements is not enough, because solutions and test data have to be prepared too. Please help us with the test data for the on-line banking problem. Here is what the banking program does.

The banking program reads several scenarios. A scenario starts with a line holding one positive integer $A$ , the number of accounts that exist when the supervision starts, $0 < A \le 100$ . Each of the next $A$ lines holds an account number, one space, and the starting balance of that account. Every line after that is one request, and a scenario holds between $0$ and $1000$ requests.

Command	Meaning	Parameters
`create`	open a new account	new account number
`deposit`	put cash into an account	account number, amount
`withdraw`	take cash out of an account	account number, amount
`transfer`	wire money between two accounts	source account, target account, amount

The last request of a scenario is followed by a line holding end and one empty line, and then the next scenario begins. A line holding 0 in place of $A$ closes the whole input.

An account number is exactly four decimal digits, then a slash, then one more digit that is the code of the bank keeping the account. Every bank has its own code. An amount is a non-negative decimal number with exactly two digits after the decimal point, at most 10000.00, written without unnecessary leading zeros, so only an amount below 1.00 starts with a zero. A starting balance uses the same notation and has no upper limit.

For every request the banking program prints one line: the command, then the amount parameter if the command has one, then a colon, one space, and the result.

create: if the same bank already keeps an account with that number, the result is already exists. Otherwise the account is opened with balance 0.00 and the result is ok.

For every command other than create, if any account number given as a parameter belongs to no account, the result is no such account. When the accounts do exist, the rules below decide the result.

deposit: the result is always ok, and the amount is added to the balance.

withdraw: if the balance is strictly lower than the amount, the result is insufficient funds. Otherwise the amount is subtracted and the result is ok.

transfer: if the two account numbers are equal, bank code included, the result is same account. Otherwise, if the balance of the source account is lower than the amount, the result is insufficient funds. Otherwise the money moves, and the result is ok when both accounts belong to the same bank or interbank when they belong to different banks.

After each scenario the banking program prints end and one empty line. After the end of the last scenario it prints one more line holding goodbye.

Your job is to build an input that makes the banking program print a given output. A huge number of inputs produce the same output, so the output section fixes one canonical shape and you print that one.

Input

The input is the complete output of one correct run of the banking program, so at least one input that produces it exists. Each scenario holds between $0$ and $1000$ result lines.

Output

Print an input for the banking program that produces exactly the given output, built in the canonical shape below.

Turn every result line of a scenario into one request. In the table, $v$ is the amount printed on the result line, copied character for character, and $k$ is the number of create requests answered with ok so far in the current scenario, this one included.

Result line	Request
`create: already exists`	`create 1000/1`
`create: ok`	`create KKKK/3`, with `KKKK` equal to $k$ written in four digits
`deposit v: ok`	`deposit 1000/1 v`
`deposit v: no such account`	`deposit 9999/9 v`
`withdraw v: ok`	`withdraw 1000/1 v`
`withdraw v: insufficient funds`	`withdraw 4000/1 v`
`withdraw v: no such account`	`withdraw 9999/9 v`
`transfer v: ok`	`transfer 1000/1 2000/1 v`
`transfer v: interbank`	`transfer 1000/1 3000/2 v`
`transfer v: same account`	`transfer 1000/1 1000/1 v`
`transfer v: insufficient funds`	`transfer 4000/1 1000/1 v`
`transfer v: no such account`	`transfer 9999/9 1000/1 v`

Every scenario declares exactly four accounts, printed before its requests in this order.

Account line	Role
`1000/1 B`	the only account that ever holds money
`2000/1 0.00`	target of every transfer inside one bank
`3000/2 0.00`	target of every transfer between two banks
`4000/1 0.00`	the account that never has enough money

$B$ is the smallest balance for which the requests above still produce the required results. Print it with exactly two digits after the decimal point and without unnecessary leading zeros.

After the requests of a scenario print end and one empty line. After the last scenario print a line holding 0.

Examples1

Example 1

Input

withdraw 20.00: ok
deposit 35.00: ok
withdraw 200.00: insufficient funds
transfer 100.50: ok
transfer 50.00: interbank
create: already exists
create: ok
transfer 100.00: same account
transfer 100.00: insufficient funds
withdraw 100.00: no such account
deposit 0.11: no such account
transfer 10000.00: no such account
end

deposit 6.92: ok
withdraw 9.68: ok
withdraw 6.64: ok
end

goodbye

Expected output

4
1000/1 135.50
2000/1 0.00
3000/2 0.00
4000/1 0.00
withdraw 1000/1 20.00
deposit 1000/1 35.00
withdraw 4000/1 200.00
transfer 1000/1 2000/1 100.50
transfer 1000/1 3000/2 50.00
create 1000/1
create 0001/3
transfer 1000/1 1000/1 100.00
transfer 4000/1 1000/1 100.00
withdraw 9999/9 100.00
deposit 9999/9 0.11
transfer 9999/9 1000/1 10000.00
end

4
1000/1 9.40
2000/1 0.00
3000/2 0.00
4000/1 0.00
deposit 1000/1 6.92
withdraw 1000/1 9.68
withdraw 1000/1 6.64
end

0