考虑一个城镇，其道路网络形成一个 $N \times M$ 的网格，相邻的交叉路口由道路连接。所有道路都是双向的。每个方向都有一个关联的数值，表示从一端行驶到另一端所需的时间。

每条道路的每个方向由一条或多条车道组成。车道可以执行以下功能之一：左转、直行、右转或它们的任意组合。但是，左转车道不能放置在直行或右转车道的右侧，直行车道不能放置在右转车道的右侧。没有掉头车道。

穿过交叉路口的规则如上图所示（假设汽车从南面进入交叉路口）。要进行左转，汽车必须位于 $L$ 条左转车道中的一条；我们将它们从左到右编号为 $1$ 到 $L$。交通规则规定，车道 $i$ 必须转入目标道路的第 $i$ 条车道（从左侧开始计数），但车道 $L$ 可以转入第 $L$ 条车道或其右侧的任何其他车道。

类似地，要直行穿过交叉路口，汽车必须位于 $S$ 条直行车道中的一条；我们将它们从左到右编号为 $1$ 到 $S$。车道 $i$ 必须进入目标道路的第 $i$ 条车道（从左侧开始计数），但车道 $S$ 可以进入第 $S$ 条车道或其右侧的任何其他车道。

要进行右转，汽车必须位于 $R$ 条右转车道中的一条。为了讨论方便，我们从右到左考虑这些车道以及目标道路的车道。我们将右转车道从右到左编号为 $1$ 到 $R$。车道 $i$ 必须转入目标道路的第 $i$ 条车道（从右侧开始计数），但车道 $R$ 可以转入第 $R$ 条车道或其左侧的任何其他车道。

保证如果存在至少一条左转/直行/右转车道，则目标道路必然存在，且有足够的车道分别容纳左转/直行/右转。穿过交叉路口所花费的时间可以忽略不计。

此外，驾驶员可以在道路中间变换车道。注意，在上述交叉路口规则中，驶入目标道路的任何合法车道不计为一次变道。变道所花费的时间可以忽略不计。

行程的起点和终点位于道路中点的最右侧车道。从中点到端点行驶所需的时间是端点到端点所需时间的一半。

你正在这个城镇经营一家名为“Safest Taxi”的出租车公司，口号是“您的安全掌握在您手中”。你让客户为他们的行程选择数字 $X$ 和 $Y$，驾驶员在完成行程时最多进行 $X$ 次左转和 $Y$ 次变道。

在给定规则的情况下，完成每次行程的最短时间是多少？

输入格式

第一行包含三个整数 $N$ ($2 \le N \le 15$)，$M$ ($2 \le M \le 15$) 和 $K$ ($1 \le K \le 3$)，由单个空格分隔。城镇的道路网络有 $N$ 个南北向交叉路口和 $M$ 个东西向交叉路口。每条道路有 $K$ 条车道。

第二行包含一个整数 $D$。城镇的道路网络有 $D$ 条路段。每一对相邻的交叉路口必须在列表中恰好出现一次。

接下来的 $D$ 行，每行描述一条路段，格式如下：

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

这描述了一条从第 $R_0$ 行第 $C_0$ 列的交叉路口到第 $R_1$ 行第 $C_1$ 列的交叉路口的道路（$0 \le R_0, R_1 < N, 0 \le C_0, C_1 < M$）。行号从北到南编号为 $0$ 到 $N-1$，列号从西到东编号为 $0$ 到 $M-1$。该路段必须连接两个相邻的交叉路口，即 $|R_0 - R_1| + |C_0 - C_1| = 1$。行驶整个路段的时间为 $T$ ($2 \le T \le 100$，$T$ 必须为偶数)。接下来的 $K$ 个字符串描述了从左到右每条车道的功能，语义如下：

• L | 仅左转
• S | 仅直行
• R | 仅右转
• LR | 左转或右转
• LS | 左转或直行
• SR | 直行或右转
• LSR | 左转、直行或右转

下一行包含一个整数 $P$ ($1 \le P \le 50$)，表示要完成的行程数量。

接下来的 $P$ 行，每行描述一个行程，格式如下：

$RS_0 \ CS_0 \ RS_1 \ CS_1 \ RD_0 \ CD_0 \ RD_1 \ CD_1 \ X \ Y$

这表示起点是路段 $(RS_0, CS_0) \to (RS_1, CS_1)$ 的中点，终点是路段 $(RD_0, CD_0) \to (RD_1, CD_1)$ 的中点。这两个路段都必须出现在上面的列表中。起点和终点都在最右侧车道上。客户要求行程中最多允许 $X$ ($0 \le X \le 4$) 次左转和 $Y$ ($0 \le Y \le 4$) 次变道。

输出格式

输出 $P$ 行。第 $i$ 行包含一个整数，表示在给定规则下完成每次行程的最短时间，如果不存在可行路线，则输出 $-1$。

样例

样例输入 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

样例输出 1

8
48
66
131
112
95

说明

样例输出的前三行在下图中进行了说明。

• 如果 $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$。