재즈 여행

이반은 재즈 밴드와 함께 대규모 유럽 순회공연을 계획하고 있다. 유럽에는 도시가 $n$개 있고, 각 도시에는 1부터 $n$까지 번호가 붙어 있다. 이반은 도시 $a_1, a_2, \ldots, a_d$에서 정확히 이 순서대로 공연을 $d$번 연다. 연속한 두 공연이 같은 도시에서 열리는 일은 없으며($a_i \ne a_{i+1}$) 어떤 도시는 여러 번 방문할 수도 있다. 투어는 시작한 도시에서 끝난다($a_1 = a_d$).

이반은 도시 $a_i$에서 $a_{i+1}$로 갈 때 항상 직항편을 탄다. 그래도 항공권을 잘 골라 사서 돈을 아끼려 한다. 항공사는 수요와 공급에 따라 요금을 정하므로 같은 두 도시 사이에서 편도 항공권이 왕복 항공권보다 비쌀 수도 있다.

살 수 있는 항공권은 두 종류다.

• 출발 도시 $a$에서 도착 도시 $b$로 가는 편도 항공권으로는 $a$에서 $b$로 한 번 날아갈 수 있다. 반대 방향으로는 쓸 수 없다.
• 출발 도시 $a$에서 도착 도시 $b$로 가는 왕복 항공권으로는 $a$에서 $b$로 한 번, $b$에서 $a$로 한 번 날아갈 수 있다. 돌아오는 구간($b$에서 $a$)은 쓰지 않아도 된다. 다만 두 구간은 순서대로 이용해야 한다. 그 항공권의 첫 구간으로 $a$에서 $b$로 먼저 날아가지 않았다면 돌아오는 구간으로 $b$에서 $a$로 날아갈 수 없다.

살 수 있는 항공권 요금 목록이 주어질 때, 이반이 투어를 마치려면 항공권에 최소 얼마를 써야 하는지 구하라. 각 요금의 항공권은 원하는 만큼 살 수 있다. 다시 말해 이반은 모든 $i = 1, 2, \ldots, d-1$에 대해 $a_i$에서 $a_{i+1}$로 직항편을 타야 한다. 주어진 요금으로 투어를 마칠 수 있다고 가정해도 된다.

첫째 줄에 유럽의 도시 수 $n$과 공연 수 $d$가 주어진다. ($2 \le n, d \le 300000$)

둘째 줄에 투어 일정 $a_1, a_2, \ldots, a_d$가 주어진다. ($1 \le a_i \le n$, $a_i \ne a_{i+1}$, $a_1 = a_d$)

셋째 줄에 항공권 요금의 수 $m$이 주어진다. ($3 \le m \le 300000$) 다음 $m$개 줄 가운데 $k$번째 줄에는 $k$번째 요금을 나타내는 네 토큰 $s_k$, $d_k$, $t_k$, $p_k$가 주어진다.

• $s_k$와 $d_k$는 각각 출발 도시와 도착 도시다. ($1 \le s_k, d_k \le n$, $s_k \ne d_k$)
• $t_k$는 대문자 O 또는 R이며, 각각 편도 항공권과 왕복 항공권을 뜻한다.
• $p_k$는 항공권 가격이며 정수다. ($1 \le p_k \le 10^9$)

이반이 계획한 투어를 마칠 수 있도록 항공권을 사는 데 필요한 최소 금액을 출력한다.