Care of Magical Creatures
Ogrid scattered bundles of cabbage on a rectangular enclosed platform, placed a small centipod there, and tasked the students with feeding this creature. The centipod is so dull that it always moves in a straight line until it encounters an obstacle or its own body. With the help of spells, the centipod can be made to turn left or right. When eating cabbage, the centipod grows in size.
Write a program that simulates feeding the centipod. The centipod moves at a speed of one cell per second. If a command is given at the beginning of the second, the centipod turns its head in the specified direction (the head turn is instantaneous), and then moves in the direction its head is facing. If no commands are given, the centipod continues moving in the same direction as in the previous second. If there is a fence of the platform or its own body ahead, the centipod stays in place; otherwise, it moves one cell forward. If there is cabbage on the cell, the length of the centipod instantly increases by one unit (the tail of the centipod does not move from its place). The head of the centipod is located on the first segment of the body and can turn at any angle multiple of 90 degrees.
Input
The first line of the input file contains two integers separated by a space – the dimensions of the platform N (1 ≤ N ≤ 100) and M (1 ≤ M ≤ 100). Then follow N lines, each containing M characters – the initial state of the platform. The symbol '.' (dot) denotes an empty cell, the symbol '@' – a cell with cabbage. The symbol '%' appears exactly once and indicates the initial position of the centipod, its length at the start of the simulation is one, and the head is directed towards the right fence. The last line contains the second-by-second record of commands spoken by the student. The symbol '-' (minus) indicates no commands at the beginning of the corresponding second, the symbol 'L' – the command "left", and the symbol 'R' – the command "right". The number of symbols in the last line does not exceed 100 000.
Output
Output N lines of M characters – the final state of the platform. The head of the centipod is depicted by the symbol '%', and the body by the symbol '#'.