Mr Cleese's now wants you to make sure the player doesn't move to places where he isn't supposed to.

Hint: please make sure you have completed csci125p014, csci125p016 before attempting this task.

In addition to the movements in csci125p016, Mr Cleese now wants you to make sure:

1. the player doesn't stand on top of the fence.
    When the player attempts to do so, you must make sure the player remains where he/she is.

2. the tree occupies only one block (its original coordinate), and the
    player can stand there.
    However, when the player is behind the tree (area covered with '*')
    on the map, the player should not be shown on the map.

3. the player may not move to any area where there is a house (any  
    part of the house, not just the original coordinate).

Input Specification

The first line will contain two integers \(N,M\) (\(1 < N,M < 20\)), indicating the dimension size.

The following \(N\) lines will each contain \(M\) integers, each the item at that coordinate. It is guaranteed that the player (denoted by \(4\)) will appear on the map, and only once.

The next line will contain an integer \(Q\), the number of movements the player is attempting to make.

This is followed by \(Q\) lines of movements, each containing a single integer in the range of \(1\) to \(4\).

Output Specification

The output should contain \(Q+1\) maps, separated by an empty line.

The first map should be the original map: before any movement has taken place.

The next \(Q\) maps are the results of every step of movement.

Each map is represented by a bitmap of \(N\) lines, \(M\) characters.

You are strongly encouraged to design your own test cases as well.

Sample Input

8 12
1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 3 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 2 0 0 0 0 1
1 0 0 0 4 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1

6
2
2
1
1
1
3

Sample Output

############
#    _     #
#   /_*    #
#   |***   #
#   *****  #
#     |    #
#   +      #
############

############
#    _     #
#   /_*    #
#   |***   #
#   *****  #
#     |    #
#   +      #
############

############
#    _     #
#   /_*    #
#   |***   #
#   *****  #
#     |    #
#   +      #
############

############
#    _     #
#   /_*    #
#   |***   #
#   *****  #
#   + |    #
#          #
############

############
#    _     #
#   /_*    #
#   |***   #
#   *****  #
#     |    #
#          #
############

############
#    _     #
#   /_*    #
#   |***   #
#   *****  #
#     |    #
#          #
############

############
#    _     #
#   /_*    #
#   |***   #
#  +*****  #
#     |    #
#          #
############