가장 안전한 택시

도로망이 $N \times M$ 격자 모양인 도시를 생각해 보자. 인접한 교차로는 도로로 연결되어 있고, 모든 도로는 양방향으로 달릴 수 있다. 각 방향에는 한 끝점에서 다른 끝점까지 이동하는 데 걸리는 시간이 주어진다.

도로의 각 방향은 하나 이상의 차선으로 이루어진다. 차선은 좌회전, 직진, 우회전 중 하나, 또는 이들의 조합 용도로 쓰인다. 다만 좌회전 차선은 직진 차선이나 우회전 차선의 오른쪽에 놓일 수 없고, 직진 차선은 우회전 차선의 오른쪽에 놓일 수 없다. 유턴 차선은 없다.

교차로 통과 규칙은 위 그림과 같다(차량이 남쪽에서 교차로로 진입하는 경우). 좌회전하려면 차량이 $L$개의 좌회전 차선 중 하나에 있어야 한다. 좌회전 차선은 왼쪽에서 오른쪽으로 $1$번부터 $L$번까지 번호를 붙인다. $i$번 차선은 목적 도로의 왼쪽에서 $i$번째 차선으로 진입해야 한다. 다만 $L$번 차선은 목적 도로의 $L$번째 차선 또는 그 오른쪽에 있는 어느 차선으로든 진입할 수 있다.

직진하려면 차량이 $S$개의 직진 차선 중 하나에 있어야 한다. 직진 차선은 왼쪽에서 오른쪽으로 $1$번부터 $S$번까지 번호를 붙인다. $i$번 차선은 목적 도로의 왼쪽에서 $i$번째 차선으로 진입해야 한다. 다만 $S$번 차선은 목적 도로의 $S$번째 차선 또는 그 오른쪽에 있는 어느 차선으로든 진입할 수 있다.

우회전하려면 차량이 $R$개의 우회전 차선 중 하나에 있어야 한다. 이 규칙에서는 우회전 차선을 오른쪽에서 왼쪽으로 $1$번부터 $R$번까지 번호를 붙인다. $i$번 차선은 목적 도로의 오른쪽에서 $i$번째 차선으로 진입해야 한다. 다만 $R$번 차선은 목적 도로의 $R$번째 차선 또는 그 왼쪽에 있는 어느 차선으로든 진입할 수 있다.

좌회전, 직진, 우회전 차선 중 하나 이상이 존재하면, 목적 도로가 반드시 있고 해당 이동을 수용할 차선 수를 갖추고 있다고 보장된다. 교차로 통과에 걸리는 시간은 무시한다.

교차로에서 목적 도로의 적법한 차선으로 진입하는 것은 차선 변경으로 치지 않는다. 운전자는 도로 중간에서 차선을 바꿀 수 있고, 차선 변경에 걸리는 시간은 무시한다.

여행은 도로 중점의 가장 오른쪽 차선에서 출발하여 가장 오른쪽 차선에서 끝난다. 중점에서 끝점까지 가는 시간은 두 끝점 사이를 가는 시간의 절반이다.

당신은 이 도시에서 '안전한 택시'라는 회사를 운영한다. 슬로건은 '당신의 안전은 당신의 손에 달려 있습니다'이다. 고객은 여행마다 수 $X$와 $Y$를 고를 수 있다. 기사는 여행을 마치는 동안 좌회전을 최대 $X$번, 차선 변경을 최대 $Y$번 한다.

이 규칙들을 따를 때 각 여행을 마치는 데 걸리는 최단 시간은 얼마인가?

첫 줄에는 세 정수 $N$ ($2 \leq N \leq 15$), $M$ ($2 \leq M \leq 15$), $K$ ($1 \leq K \leq 3$)를 공백 하나로 구분해 입력한다. 도시에는 남북 방향으로 $N$개, 동서 방향으로 $M$개의 교차로가 있다. 각 도로에는 $K$개의 차선이 있다.

둘째 줄에는 도로 구간의 개수 $D$를 하나의 정수로 입력한다. 인접한 교차로의 모든 쌍은 목록에 정확히 한 번씩 나타난다.

이어지는 $D$개의 줄은 각각 다음 형식으로 한 구간을 나타낸다.

$R_0$ $C_0$ $R_1$ $C_1$ $T$ $L_0$ $L_1$ ... $L_{K-1}$

이 구간은 행 $R_0$, 열 $C_0$의 교차로에서 행 $R_1$, 열 $C_1$의 교차로로 간다($0 \leq R_0, R_1 < N$, $0 \leq C_0, C_1 < M$). 행은 북쪽에서 남쪽으로 $0$부터 $N-1$까지, 열은 서쪽에서 동쪽으로 $0$부터 $M-1$까지 번호를 붙인다. 두 교차로는 서로 인접해야 하며, $|R_0 - R_1| + |C_0 - C_1| = 1$을 만족한다. 구간 전체를 지나는 데 $T$의 시간이 걸린다($2 \leq T \leq 100$, $T$는 짝수). 이어지는 $K$개의 토큰은 왼쪽에서 오른쪽 순서로 각 차선의 용도를 나타낸다.

다음 줄에는 여행의 개수 $P$ ($1 \leq P \leq 50$)를 하나의 정수로 입력한다. 이어지는 $P$개의 줄은 각각 다음 형식으로 한 여행을 나타낸다.

$R_{S0}$ $C_{S0}$ $R_{S1}$ $C_{S1}$ $R_{D0}$ $C_{D0}$ $R_{D1}$ $C_{D1}$ $X$ $Y$

여행은 구간 $(R_{S0}, C_{S0}) \to (R_{S1}, C_{S1})$의 중점에서 출발하여 구간 $(R_{D0}, C_{D0}) \to (R_{D1}, C_{D1})$의 중점에서 끝난다. 두 구간은 위 목록에 있다. 출발점과 도착점은 모두 가장 오른쪽 차선 위에 있다. 고객이 허용하는 좌회전은 최대 $X$번($0 \leq X \leq 4$), 차선 변경은 최대 $Y$번($0 \leq Y \leq 4$)이다.

$P$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 여행을 이 규칙들에 따라 마치는 최단 시간을 출력한다. 가능한 경로가 없으면 $-1$을 출력한다.

예제 출력의 처음 세 줄은 아래 그림에 나타나 있다.

• $X = 1$이고 $Y = 1$이면 최단 경로는 빨간색이다. E에 도달하기 전에 차선을 바꾸고 좌회전한다. 총 시간은 $8/2+8/2=8$이다.
• $X = 1$이고 $Y = 0$이면 최단 경로는 초록색이다. E-F-I-H-E를 거쳐 좌회전한다. 총 시간은 $8/2+16+8+8+8+8/2=48$이다.
• $X = 0$이고 $Y = 0$이면 최단 경로는 파란색이다. E-B-C-F-E를 거친다. 총 시간은 $8/2+16+16+8+18+8/2=66$이다.