Problem G
Safest Taxi

Consider a town whose road network forms an $N \times M$ grid, where adjacent intersections are connected by roads. All roads are bi-directional. Each direction has an associated number - the time needed to travel from one end-point to another.

Each direction of each road consists of one or more lanes. A lane can serve one of the following functions: left-turn, straight, right-turn, or any combination of them. However, a left-turn lane cannot be placed to the right of a straight or right-turn lane, and a straight lane cannot be placed to the right of a right-turn lane. There are no U-turn lanes.

The rules for crossing intersections are illustrated in the above figure (suppose a car enters the intersection from the south). To make a left turn, it must be in one of the $L$ left-turn lanes; let’s number them $1$ through $L$ from left to right. The traffic rule says Lane $i$ must turn into the $i$-th lane (counting from the left) of the target road, except that Lane $L$ may turn into the $L$-th lane or any other lanes to its right.

Similarly, to go straight through an intersection, the car must be in one of the $S$ straight lanes; let’s number them $1$ through $S$ from left to right. Lane $i$ must go into the $i$-th lane (counting from the left) of the target road, except that Lane $S$ may go into the $S$-th lane or any other lanes to its right.

To make a right turn, the car must be in one of the $R$ right-turn lanes. For the convenience of discussion, we consider these lanes and those of the target road from right to left. Let’s number the right-turn lanes $1$ through $R$ from right to left. Lane $i$ must turn into the $i$-th lane (counting from the right) of the target road, except that Lane $R$ may turn into the $R$-th lane or any other lanes to its left.

It is guaranteed that if at least one left-turn / straight / right-turn lane is present, the target road must exist and have enough lanes to accommodate the left turn / straight / right turn, respectively. The time spent on crossing intersections is negligible.

In addition, a driver may change lanes in the middle of a road. When changing lanes, the taxi can only go into a singlee neighboring lane. Note that in the above rules for intersections, it doesn’t count as a lane change to drive into any of the legal lanes of the target road. The time spent on lane changes is negligible.

A trip starts and ends at the rightmost lane of the midpoint of roads. The time needed to travel midpoint-to-endpoint is half of endpoint-to-endpoint.

You are running a taxi company called “Safest Taxi” in this town, with the slogan “your safety is in your hands”. You let your customers choose the numbers $X$ and $Y$ for their trip, and the driver will make at most $X$ left turns and $Y$ lane changes to accomplish the trip.

What is the shortest time to fulfill each trip given the rules?

Input

The first line consists of three integers $N$ ($2 \leq N \leq 15$), $M$ ($2 \leq M \leq 15$) and $K$ ($1 \leq K \leq 3$), separated by a single space. The town’s road network has $N$ intersections north-south and $M$ intersections west-east. Each road has $K$ lanes.

The second line consists of a single integer $D$. The town’s road network has $D$ road segments. Every adjacent pair of intersections must appear in the list exactly once.

Each of the next $D$ lines describes a road segment with the following format:

This describes a road segment going from the intersection at row $R_0$ column $C_0$ to the intersection at row $R_1$ column $C_1$ ($0 \leq R_0,R_1<N$, $0 \leq C_0,C_1<M$). Rows are numbered $0$ through $N-1$ from north to south, and columns are numbered $0$ through $M-1$ from west to east. The segment must connect two adjacent intersections, i.e., $\mid R_0 - R_1 \mid + \mid C_0 - C_1\mid = 1$. The time to travel through the entire segment is $T$ ($2 \leq T \leq 100$, $T$ must be an even number). The next $K$ strings describe the function of each of the $K$ lanes, from left to right, with the following semantics:

L $\mid $ Left-turn only

S $\mid $ Straight only

R $\mid $ Right-turn only

LR $\mid $ Left-turn or right-turn

LS $\mid $ Left-turn or straight

SR $\mid $ Straight or right-turn

LSR $\mid $ Left-turn, straight or right-turn

The next line consists of a single integer $P$ ($1 \leq P \leq 50$), the number of trips to fulfill.

Each of the next $P$ lines describes a trip with the following format:

This indicates that the starting point is the midpoint of segment ($R_{S0}, C_{S0}$) $\to $ ($R_{S1}, C_{S1}$), and the destination is the midpoint of segment ($R_{D0}, C_{D0}$) $\to $ ($R_{D1}, C_{D1}$). Both segments must appear in the above list. Both the starting point and the destination are on the rightmost lane. The customer requests that at most $X$ ($0 \leq X \leq 4$) left turns and $Y$ ($0 \leq Y \leq 4$) lane changes are allowed for the trip.

Output

Output $P$ lines. The $i$-th line contains a single integer which is the shortest time to fulfill each trip given the rules, or $-1$ if no feasible route exists.

Sample Explanation

The first three lines of the sample output are illustrated in the figure below.

• If $X = 1$ and $Y = 1$, the shortest path is shown in red: make a lane change before reaching E and make a left turn. The total time is $8/2+8/2=8$;

• If $X = 1$ and $Y = 0$, the shortest path is shown in green: go through E-F-I-H-E and make a left turn. The total time is $8/2+16+8+8+8+8/2=48$;

• If $X = 0$ and $Y = 0$, the shortest path is shown in blue: go through E-B-C-F-E. The total time is $8/2+16+16+8+18+8/2=66$.

3 3 2
24
0 0 0 1 6 S R
0 1 0 0 8 L L
0 1 0 2 16 R R
0 2 0 1 18 LS S
0 0 1 0 8 LS S
1 0 0 0 8 R R
0 1 1 1 10 LS SR
1 1 0 1 16 L R
0 2 1 2 8 S R
1 2 0 2 8 L L
1 0 1 1 6 L SR
1 1 1 0 8 L R
1 1 1 2 16 L R
1 2 1 1 18 L SR
1 0 2 0 8 L L
2 0 1 0 8 S R
1 1 2 1 10 L R
2 1 1 1 8 LS SR
1 2 2 2 8 R R
2 2 1 2 8 LS S
2 0 2 1 10 LS S
2 1 2 0 12 R R
2 1 2 2 6 L L
2 2 2 1 8 S SR
6
2 1 1 1 1 1 1 0 1 1
2 1 1 1 1 1 1 0 1 0
2 1 1 1 1 1 1 0 0 0
0 1 0 2 0 2 0 1 2 0
1 0 0 0 0 0 1 0 2 0
2 1 2 0 2 0 2 1 2 0

8
48
66
131
112
95