Jazz Journey

Ivan is planning a large European tour with his jazz band. There are $n$ cities in Europe, numbered with integers $1$ through $n$. Ivan is planning $d$ concerts in cities $a_1, a_2, \ldots, a_d$ in that exact order. Two consecutive concerts are never in the same city ($a_i \ne a_{i+1}$), some cities may be visited many times, and the tour ends in the same city where it began ($a_1 = a_d$).

Ivan always takes a direct flight between cities $a_i$ and $a_{i+1}$. However, he wants to be smart with his ticket purchases to save money. Airlines price tickets based on supply and demand, so it may happen, for example, that one-way tickets are more expensive than round trip tickets between the same cities.

There are two kinds of tickets available for purchase:

• A one-way ticket from origin city $a$ to destination city $b$ can be used to fly from $a$ to $b$ once. It cannot be used in the opposite direction.
• A round trip ticket from origin city $a$ to destination city $b$ can be used to fly once from $a$ to $b$ and once from $b$ to $a$. The return segment (from $b$ to $a$) does not need to be used. However, the segments have to be flown in order: Ivan may not use the return segment of a ticket to fly from $b$ to $a$ unless he has already used the first segment of that ticket to fly from $a$ to $b$.

You are given a list of available airfares. Find the least amount of money Ivan needs to spend on tickets to complete his journey. Ivan can purchase any number of tickets for each airfare. Once again, Ivan needs to take a direct flight from $a_i$ to $a_{i+1}$ for every $i = 1, 2, \ldots, d-1$. You may assume that the journey can be completed using the given airfares.

The first line contains two integers $n$ and $d$ ($2 \le n, d \le 300000$): the number of cities in Europe and the number of concerts.

The second line contains the integers $a_1, a_2, \ldots, a_d$ ($1 \le a_i \le n$, $a_i \ne a_{i+1}$, $a_1 = a_d$): the planned tour schedule.

The third line contains an integer $m$ ($3 \le m \le 300000$): the number of airfares. The $k$-th of the following $m$ lines contains four tokens $s_k$, $d_k$, $t_k$, $p_k$ that describe the $k$-th airfare:

• $s_k$ and $d_k$ ($1 \le s_k, d_k \le n$, $s_k \ne d_k$) are the origin and the destination city, respectively.
• $t_k$ is an uppercase letter O or R, denoting a one-way or a round trip ticket, respectively.
• $p_k$ ($1 \le p_k \le 10^9$) is the ticket price, an integer.

Output the least amount of money needed to purchase tickets that allow Ivan to complete the planned tour.