The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Beta Round 82 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

implementation

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Treasure Island

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOur brave travelers reached an island where pirates had buried treasure. However as the ship was about to moor, the captain found out that some rat ate a piece of the treasure map.

The treasure map can be represented as a rectangle *n* × *m* in size. Each cell stands for an islands' square (the square's side length equals to a mile). Some cells stand for the sea and they are impenetrable. All other cells are penetrable (i.e. available) and some of them contain local sights. For example, the large tree on the hills or the cave in the rocks.

Besides, the map also has a set of *k* instructions. Each instruction is in the following form:

"Walk *n* miles in the *y* direction"

The possible directions are: north, south, east, and west. If you follow these instructions carefully (you should fulfill all of them, one by one) then you should reach exactly the place where treasures are buried.

Unfortunately the captain doesn't know the place where to start fulfilling the instructions — as that very piece of the map was lost. But the captain very well remembers that the place contained some local sight. Besides, the captain knows that the whole way goes through the island's penetrable squares.

The captain wants to know which sights are worth checking. He asks you to help him with that.

Input

The first line contains two integers *n* and *m* (3 ≤ *n*, *m* ≤ 1000).

Then follow *n* lines containing *m* integers each — the island map's description. "#" stands for the sea. It is guaranteed that all cells along the rectangle's perimeter are the sea. "." stands for a penetrable square without any sights and the sights are marked with uppercase Latin letters from "A" to "Z". Not all alphabet letters can be used. However, it is guaranteed that at least one of them is present on the map. All local sights are marked by different letters.

The next line contains number *k* (1 ≤ *k* ≤ 10^{5}), after which *k* lines follow. Each line describes an instruction. Each instruction possesses the form "*dir* *len*", where *dir* stands for the direction and *len* stands for the length of the way to walk. *dir* can take values "N", "S", "W" and "E" for North, South, West and East correspondingly. At that, north is to the top, South is to the bottom, west is to the left and east is to the right. *len* is an integer from 1 to 1000.

Output

Print all local sights that satisfy to the instructions as a string without any separators in the alphabetical order. If no sight fits, print "no solution" without the quotes.

Examples

Input

6 10

##########

#K#..#####

#.#..##.##

#..L.#...#

###D###A.#

##########

4

N 2

S 1

E 1

W 2

Output

AD

Input

3 4

####

#.A#

####

2

W 1

N 2

Output

no solution

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/09/2023 08:15:53 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|