ICPC World Finals Day 5

Mr. Tee got lost in the city of R country. The trouble is that the streets are similar, so I have no idea where I am now. Country R is "sorry", so you have to return to the hotel before being attacked by the enemy. Fortunately, I only remember how it turned, so let's go random.

problem

\ (w \ times h \) There is a two-dimensional grid-like map of squares. Let the coordinates of the upper left cell be \ ((1, 1) \) and the coordinates of the lower right cell be \ ((w, h) \). The map is surrounded by walls, and \ (n \) obstacles are coordinated \ ((x_ {i}, y_ {i}) (1 \ leq i \ leq n) \) Is placed in. In addition, the instruction sequence \ (r_ {1} r_ {2} \ cdots r_ {m} \) and the target coordinates \ ((g_ {x}, g_ {y}) \) are given. After setting the start coordinates and the direction of travel, the pedestrian starts walking according to the following movement rules.

1. Initialize the counter to \ (i = 1 \) and set the start coordinates and travel direction (up / down / left / right).
2. Go straight until you meet a wall / obstacle.
3. Do one of the following in front of the wall / obstacle.
4. a. \ (i> m \), that is, end walking if there is no command.
5. b. If the command \ (r_ {i} \) is L, turn left, and if R, turn right.
6. Increment \ (i \).
7. Return to 2.

If the coordinates (including the start coordinates) passed from the start of walking to the end of walking include the target coordinates \ ((g_ {x}, g_ {y}) \), the pedestrian has reached the destination. Interpret as. Find out how many combinations of start coordinates and travel directions can reach your destination. However, it is assumed that obstacles and coordinates outside the map cannot be set as the start coordinates. (The target coordinates can be set.)

input

w h gx gy n
x1 y1
...
xn yn
r1r2… rm

Map width \ (w \), height \ (h \), destination x coordinate \ (g_ {x} \), destination y coordinate \ (g_) on the first line {y} \), the number of obstacles \ (n \) are given separated by blanks. From the second line to the \ (n + 1 \) line, the coordinates of each obstacle \ ((x_ {i}, y_ {i}) \) are given separated by blanks. The instruction column \ (r_ {1} r_ {2} \ cdots r_ {m} \) of length \ (m \) is given in the \ (n + 2 \) line.

output

Output the number of combinations of starting coordinates and traveling directions on one line so that you can reach your destination.

Constraint

• All inputs are integers
• \ (2 \ leq w, h \ leq 10 ^ {5} (= 100000) \)
• \ (0 \ leq n \ leq 10 ^ {5} (= 100000) \)
• \ (1 \ leq g_ {x}, x_ {i} \ leq w \)
• \ (1 \ leq g_ {y}, y_ {i} \ leq h \)
• \ ((x_ {i}, y_ {i}) \ not = (g_ {x}, g_ {y}) (1 \ leq i \ leq n) \)
• \ ((x_ {i}, y_ {i}) \ not = (x_ {j}, y_ {j}) (i \ not = j) \)
• \ (r_ {i} \ in \ {L, R \} (1 \ leq i \ leq m) \)
• \ (1 \ leq m \ leq 20 \)

Input / output example

Input 1

3 3 3 2 2
1 1
twenty two
RL

Output 1

9

In addition to the following 5 types of walking, walking (4 types) starting from the target coordinates passes through the target coordinates.

http://k-operafan.info/static/uecpc2013/files/lost_sample_1.png

Input 2

4 4 3 1 4
1 1
3 2
13
4 3
RR

Output 2

13

Walking starting from the following start coordinates / traveling direction passes through the target coordinates.

http://k-operafan.info/static/uecpc2013/files/lost_sample_2.png

Input 3

100000 100000 46597 49716 17
38713 77141
46598 78075
66177 49715
58569 77142
48303 12742
32829 65105
32830 78076
70273 27408
48302 21196
27119 54458
38714 65104
46598 54457
27118 12743
60242 21197
60241 1101
58568 27409
93581 1100
LLRRLLLLRRLL

Output 3

647505

Example

Input

w h g

Output

9

见题面

见题面