SUSTech is now made into the game BABA IS YOU! For those who knows this game, the rules are slightly different.

There are many objects in SUSTech. Some objects in SUSTech can be pushed, while others cannot.

When you send a move command towards a direction, all objects currently under your control will try to move in that direction by 1 step.
The force of pushing will continue to pass to the objects ahead. If at last an empty grid is reached, those objects will together move one step ahead in that direction.
However, if a STOP (i.e., not pushable) object is reached before an empty grid, all the things affected in this process stay still.

There are 26 types of normal objects represented in lowercase characters ("a"-"z"), empty grids represented in points ("."), and language objects ("A"-"Z","#","+","@","$","=").
There are three types of language objects: "OBJECT", "IS", and "PROPERTY".

"A"-"Z" stands for normal object types represented in their corresponding lowercase formats. Their type is "OBJECT".
"#" stands for STOP. It's type is "PROPERTY". It means objects with this property is not pushable unless other rules overwrite it to do so.
"+" stands for PUSH. It's type is "PROPERTY". It means objects with this property is pushable. This rule overwrites the STOP property.
"@" stands for YOU. It's type is "PROPERTY". It means objects with this property is currently under your control. This rule overwrites the PUSH and STOP property.
"$" stands for WIN. It's type is "PROPERTY". It means the object is currently a "good" object. When any object on the map of this property is at the same time a YOU object,
this map is currently in a "good" state.
"=" stands for IS. It's type is "IS".

An assertion is made up of three adjacent language objects: one OBJECT, one IS, and one PROPERTY, from left to right or up to down. After each move finishes, the assertions may change.
New assertions will start working from the next move, until it is broken. A type of object may have multiple properties. There may be multiple assertions of the same meaning.

Normal objects that are not involved in any assertion should be treated as STOP.
Language objects should always be treated as PUSH.

We use "<" ">" "^" "v" to represent the move command sequence in a string.
"<" stands for "LEFT".
">" stands for "RIGHT".
"^" stands for "UP".
"v" stands for "DOWN".

You need to output a sequence to represent whether the map is in a "good" state before start and after each move.
Use "*" for "good" state and "-" otherwise.
After finishing the command sequence, you need to output the state of the map.

It is promised that no objects will move out of the limited map border.

The input consists of:
    The first line contains 2 integers N and M (N, M >= 1) splited with a space.
    Then N lines of string of length M representing the initial state of the map.
    At last a line containing a non-empty string of length L representing the move command sequence (L <= 300000).
    It is guaranteed that N*M*L <= 300000.
    It is guaranteed that the input file is no more than 606060 Bytes.

Firstly, output a string in one line to show the "good" state. It should be one character longer than the move command sequence.
Then output N lines of string of length M as the format of input, showing the final state of the map.

10 10
xxxxxxxxxx
x...P....x
x..R=@...x
x..P$....x
x........x
x..rrrr..x
x..rrprRRx
x..rrrr=.x
x......+#x
xxxxxxxxxx
<^^v>><^^^>^^^<<<<

---*************---
xxxxxxxxxx
x..RP....x
xP=@p....x
x.rr$r...x
x.rrr.r..x
x.rrr....x
x......RRx
x.......=x
x....r.+#x
xxxxxxxxxx

    At first, objects of type "r" are under control, because "R=@" (which overwrites "R=+").
    
    After move #03, objects of type "p" are under control, because "P=@".
    
    At the same time "P=$" and an object of type "p" exists, so the map is in a "good" state.
    
    After move #06, objects of type "r" are not pushable anylonger, because "R=#".
    
    Move #10 does not change anything, because the object of type "p" is trying to push "r", but "R=#".
    
    After move #16, the map is not in a "good" state anylonger.
    
    Move #18 does not change anything, because the object of type "x" should be treated as "X=#" by default, though no such assertions exist.

    After each step, the map state will be as the following image:

Please read paragraph 5 carefully and check your program carefully before submission.