401378: GYM100425 G Free Wi-Fi

The National Library of France is one of the largest libraries in the world. But not only collections of rare books attracts tourists there. Many of them visit the library just to use the free Wi-Fi...

The library building can be represented as a rectangular field consisting of N × M cells. Each cell can be one of three types:

1. an obstacle denoted by "#",
2. a corridor denoted by ".",
3. a room denoted by a digit from 1 to 5 depending on the room type (the numbers may be repeated).

Visitors can pass between any two cells that share a side, but can not pass into any cell with an obstacle.

Wi-Fi coverage in the library is quite weak, so in the rooms and corridors, there are some visitors with gadgets that are walking around the library looking for a place with good signal strength.

A certain tourist came to the library with his friends to use the free internet, and after a long search, he found a place with good signal strength. Due to poor knowledge of French language, the tourist had troubles to identify this location. Nevertheless, he decided to tell his friends about this place and went out in search of them. To remember his path, he decided to record how many cells and in what direction he passed. Also, he decided to record a sequence A of room types he visited, but this part was not treated very carefully, so he may miss the numbers of some visited rooms.

While the tourist was trying to find his friends, he was forced to leave the building because it was late and the library has closed.

The next day, the tourist went to the library again. Given the map of the library, he decided to find the same place again.

The room must satisfy the following criteria:

1. If the tourist starts the movement from this room and strictly follows his records, he will never walk out of the library or go try to move into an obstacle.
2. If the tourist will record the sequence B of visited room types during his way, A must be a subsequence of B.

You need to determine how many rooms in the library will satisfy the criteria above.

The first line of the input contains two integers N and M (1 ≤ N, M ≤ 1000) which are the horizontal and vertical dimensions of the library's map.

Then map itself follows: each of next N lines contains exactly M characters. Valid characters are "#", ".", "1", "2", "3", "4" and "5". The lines are ordered from top to bottom, the characters in each line are ordered from left to right.

Then follows a line containing the number of tourist's movements K (1 ≤ K ≤ 100).

The following K lines specify the tourist's movements. Each movement is described by a pair of integers C_i and P_i where C_i is a character indicating the direction of travel ("L" for moving to the left, "R" to the right, "U" up and "D" down), and P_i (1 ≤ P_i ≤ 999) is the number of cells travelled in the given direction.

The last line contains a sequence A of digits: the types of rooms listed by tourist on the first day (1 ≤ |A| ≤ 100, 1 ≤ A_i ≤ 5).

Print one integer: the number of rooms, which satisfy all requirements from the problem statement. Note that it may happen that the tourist made an error recording the sequence A. In that case, the number of rooms satisfying the requirements may be zero.

4 5
22.#.
1211#
..#.1
.#122
2
L 2
U 1
121

1

4 5
..3#.
213.#
.#33#
1214.
3
L 1
R 2
U 1
1213

3

In the first example, only the room (2, 3) in row 2 and column 3 fits.

In the second example, three rooms fit: (2, 2), (4, 2) and (4, 3).