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 bidirectional. Each direction has an associated number  the time needed to travel from one endpoint to another.
Each direction of each road consists of one or more lanes. A lane can serve one of the following functions: leftturn, straight, rightturn, or any combination of them. However, a leftturn lane cannot be placed to the right of a straight or rightturn lane, and a straight lane cannot be placed to the right of a rightturn lane. There are no Uturn 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$ leftturn 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$ rightturn lanes. For the convenience of discussion, we consider these lanes and those of the target road from right to left. Let’s number the rightturn 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 leftturn / straight / rightturn 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 midpointtoendpoint is half of endpointtoendpoint.
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 northsouth and $M$ intersections westeast. 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:
\[ R_0\; C_0\; R_1\; C_1\; T\; L_0\; L_1 ... L_{K1} \]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 $N1$ from north to south, and columns are numbered $0$ through $M1$ 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 $ Leftturn only
S $\mid $ Straight only
R $\mid $ Rightturn only
LR $\mid $ Leftturn or rightturn
LS $\mid $ Leftturn or straight
SR $\mid $ Straight or rightturn
LSR $\mid $ Leftturn,
straight or rightturn
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:
\[ R_{S0}\; C_{S0}\; R_{S1}\; C_{S1}\; R_{D0}\; C_{D0}\; R_{D1}\; C_{D1}\; X\; Y \]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 EFIHE 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 EBCFE. The total time is $8/2+16+16+8+18+8/2=66$.
Sample Input 1  Sample Output 1 

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 