RPG Extreme

Taehee has been playing an RPG lately. It is a classic RPG: the hero fights through a dungeon, defeats monsters, collects items, and levels up to defeat the boss monster.

The game takes place on an N×M two-dimensional grid. Each cell can contain one of the following.

• Empty cell (.): The hero can enter freely. The hero (@) starts on an empty cell.
• Wall (#): A blocked cell. The hero cannot move into it.
• Item box (B)
  • An item box holds one piece of equipment.
  • Equipment is one of three types: weapon (W), armor (A), or accessory (O). The capital letter is the name of the type.
  • When the hero opens a box, a weapon or armor replaces the current one of that type. An accessory is worn only if a slot is free and the hero is not already wearing an accessory with the same effect. Accessories are explained below.
  • Once a box is opened, its cell becomes empty. The hero then moves onto the cell the box was on.
• Spike trap (^)
  • Stepping on a spike trap deals 5 damage. The hero can die from this damage.
  • A trap does not disappear after it is stepped on.
  • If the hero is on a trap, cannot move in the commanded direction, and stays in place, the trap counts as stepped on again.
• Monster (&)
  • A monster has a name made of upper and lower case letters, and integer values for attack, defense, HP, and the experience gained by defeating it.
  • Entering a monster's cell starts a battle. The hero always attacks first, and the two sides take turns. Each attack deals max(1, attacker's attack - defender's defense) damage. The battle ends immediately when one side's HP is 0 or below.
  • When a monster dies, its cell becomes empty. If the hero wins, the hero moves onto that cell.
  • From the start of a battle until one side dies, everything happens within one turn.
• Boss monster (M)
  • Works the same as a monster. The goal of the game is to defeat the boss monster.

The hero starts on one empty cell. The hero's stats are as follows.

• HP, attack, and defense are integers. They start at HP 20, attack 2, and defense 2.
• Experience: The hero starts at level 1. Going from level N to N+1 requires 5×N experience.
  • On level up, maximum HP rises by 5, attack and defense each rise by 2, and HP is fully restored.
  • Leftover experience is discarded on level up. For example, if 3 more experience is needed and the hero gains 5, the hero levels up, the remaining 2 is discarded, and the experience becomes 0.
• Weapon: Only one can be equipped. Each weapon adds its attack value to the hero's attack.
  • A weapon's attack is applied before every other attack boost. So every other attack boost also multiplies the weapon's attack.
• Armor: Only one can be equipped. Each armor adds its defense value to the hero's defense.
• Accessory: Up to 4 can be equipped, but at most one of each effect. The effects are:
  • HP Regeneration (HR): Each battle won restores 3 HP. HP cannot exceed maximum HP.
  • Reincarnation (RE): When the hero dies, this accessory is destroyed. The hero is revived at full HP and sent back to the starting cell. Level and equipment do not change. If a monster was being fought, its HP is restored to maximum. If the hero obtains this accessory again after it is destroyed, the hero wears it again.
  • Courage (CO): In every battle, the first attack uses double attack (including the weapon). So every first attack deals max(1, attack×2 - monster's defense) damage.
  • Experience (EX): Experience gained is multiplied by 1.2. Fractions are dropped.
  • Dexterity (DX): Damage from spike traps is fixed at 1. If worn with Courage, the Courage attack effect is applied triple instead of double.
  • Hunter (HU): When the hero enters a battle with the boss monster, HP is restored to maximum. The boss monster's first attack deals 0 damage.
  • Cursed (CU): Has no effect but takes up an accessory slot.

Each turn of the hero proceeds in this order.

• The hero moves one cell up, down, left, or right.
• If the cell is empty, nothing happens. If it has an item box, spike trap, monster, or boss monster, the hero acts as described above.

The hero moves one cell at a time, up, down, left, or right. The moves are given in advance as one string of L, R, U, and D. L is left, R is right, U is up, and D is down. If a command cannot be carried out (into a wall, or off the grid), the hero stays where it is.

The game ends when the boss monster is defeated, when the hero dies from battle or a spike trap (HP 0 or below), or when all commands are used up. If the boss is defeated, the hero gains the boss's experience, and any level up and accessory effects are processed before the game ends. If the game ends before the input runs out, the remaining commands are ignored. After the game ends, print the result in this order.

• Grid state: N lines of M characters.
  • Hero: @. Whatever is on the hero's cell (such as a trap) is shown as @. If the hero dies, the hero disappears from the grid, so a lost game shows no @.
  • Empty cell: .
  • Wall: #
  • Non-boss monster (if alive): &
  • Boss monster (if alive): M
  • Spike trap: ^
  • Item box (if not opened): B
• Passed Turns : T, where T is the number of turns that passed. The game starts at turn 0. So if the game ends after the first move, one turn has passed.
• Hero status at the end:
  • LV : N, where N is the current level.
  • HP : REM/CUR, where REM is current HP and CUR is maximum HP. If current HP is below 0, REM is 0.
  • ATT : N+W, where N is attack without the weapon and W is the weapon's attack (0 if there is no weapon).
  • DEF : N+A, where N is defense without armor and A is the armor's defense (0 if there is no armor).
  • EXP : CUR/MAX, where CUR is current experience and MAX is the total experience needed for the next level.
• Result:
  • Boss monster defeated: YOU WIN!
  • Hero died: YOU HAVE BEEN KILLED BY S.. If the hero died in battle, S is the monster's name. If the hero died from a spike trap, S is "SPIKE TRAP".
  • Input finished: Press any key to continue.

The sample outputs show these formats more clearly. The contents of each item box and the stats of each monster are given as input, described below.

The first line contains the grid size N and M (1 ≤ N, M ≤ 100, 2 ≤ N×M).

The next N lines contain the grid, with M characters per line. Every character is one of the cell types described above.

There is exactly one boss monster (M) and exactly one hero (@).

The next line contains a string S made of L, R, U, and D (1 ≤ |S| ≤ 5,000). The hero executes the commands in S from the first character.

Let K be the number of monsters on the grid, including the boss monster. The next K lines describe each monster in this format.

• R C S W A H E (1 ≤ R ≤ N, 1 ≤ C ≤ M, 1 ≤ |S| ≤ 10, 1 ≤ W, A, H, E ≤ 20)
  • The monster is in row R, column C. A monster is guaranteed to be on this cell.
  • S is the monster's name, a string of 1 to 10 upper and lower case letters. All monster names, including the boss, are different.
  • W is the monster's attack, A is its defense, H is its maximum HP, and E is the experience gained by defeating it.

Each monster's information is given exactly once.

Let L be the number of item boxes on the grid. The next L lines describe each box in this format.

• R C T S (1 ≤ R ≤ N, 1 ≤ C ≤ M, T is W, A, or O)
  • The item box is in row R, column C. An item box is guaranteed to be on this cell.
  • If T is W or A, S is an integer N (1 ≤ N ≤ 10). For W, the box holds a weapon with attack N. For A, the box holds armor with defense N.
  • If T is O, S is one of HR, RE, CO, EX, DX, HU, or CU, which is the accessory with that effect. See the description above for details.

Each item box's information is given exactly once.

Print the final state of the grid after the game ends, as N lines of M characters.

On line N+1, print the number of turns that passed in the form Passed Turns : T.

From line N+2 to line N+6, print the hero's status in the format shown in the sample outputs. The meaning of each value is described above.

On line N+7, print the result of the game in the format described above.

The first three sample outputs show the three possible game results, so they are a useful reference.