Ivan 正在为他的爵士乐队策划一场大型欧洲巡演。欧洲共有 $n$ 个城市，编号为 $1$ 到 $n$。Ivan 计划在城市 $a_1, a_2, \dots, a_d$ 举办 $d$ 场音乐会，且必须严格按照此顺序进行。他不会连续在同一个城市举办两场音乐会（$a_i \neq a_{i+1}$），可能会多次访问某些城市，并最终在出发的城市结束巡演（$a_1 = a_d$）。

Ivan 总是乘坐直飞航班往返于城市 $a_i$ 和 $a_{i+1}$ 之间。然而，为了省钱，他试图在购买机票时精打细算。如你所知，航空公司的票价基于供需关系，例如，同一城市间的单程票可能比往返票更贵。

通常，有两种机票可供购买： 从出发城市 $a$ 到目的地城市 $b$ 的单程票，可用于从 $a$ 到 $b$ 飞行一次（不能反向使用）。 从出发城市 $a$ 到目的地城市 $b$ 的往返票，可用于从 $a$ 到 $b$ 飞行一次，以及从 $b$ 到 $a$ 飞行一次。返程航段（从 $b$ 到 $a$）不一定要使用。但是，航段必须按顺序飞行——除非 Ivan 已经使用了该票的第一航段从 $a$ 飞往 $b$，否则他不能使用该票的返程航段从 $b$ 飞往 $a$。

给定一份可用机票的列表，请找出 Ivan 完成旅程所需花费的最少金额。对于每种机票，Ivan 可以购买任意数量。再次强调，对于每个 $i = 1, 2, \dots, d-1$，Ivan 都需要乘坐从 $a_i$ 到 $a_{i+1}$ 的直飞航班。你可以假设使用这些机票完成旅程是可能的。

输入格式

第一行包含两个整数 $n$ 和 $d$ ($2 \le n, d \le 300\,000$)，分别表示欧洲的城市数量和音乐会场次。下一行包含整数 $a_1, a_2, \dots, a_d$ ($1 \le a_i \le n, a_i \neq a_{i+1}, a_1 = a_d$)，表示计划的巡演行程。

接下来一行包含一个整数 $m$ ($3 \le m \le 300\,000$)，表示机票种类数量。接下来的 $m$ 行中，第 $k$ 行包含四个标记 $s_k, d_k, t_k, p_k$，描述第 $k$ 种机票： $s_k$ 和 $d_k$ ($1 \le s_k, d_k \le n, s_k \neq d_k$) 分别是出发城市和目的地城市。 $t_k$ 是大写字母 “O” 或 “R”，分别表示单程票或往返票。 * $p_k$ ($1 \le p_k \le 10^9$) 是机票价格，为一个整数。

输出格式

输出 Ivan 完成计划巡演所需购买机票的最少金额。

样例

样例输入 1

2 5
1 2 1 2 1
4
1 2 R 6
1 2 O 3
2 1 O 3
1 2 R 5

样例输出 1

10

样例输入 2

4 10
1 2 3 1 2 1 3 2 4 1
9
2 4 O 10
1 3 R 1
3 1 R 10
2 3 R 20
1 2 R 10
1 2 O 20
2 3 O 5
3 2 O 5
4 1 O 10

样例输出 2

60