스위치

농부 미르코는 소를 키우기 시작했다. 미르코에게는 길고 곧은 도로를 따라 늘어선 외양간이 $N$개 있고, 외양간에는 1부터 $N$까지 번호가 붙어 있다. 매일 아침에는 모든 외양간 문을 열어야 하고, 저녁에는 모두 닫아야 한다. 아침이 시작될 때 모든 문은 닫혀 있고, 저녁이 시작될 때 모든 문은 열려 있다.

미르코의 집에는 1부터 $M$까지 번호가 붙은 스위치가 $M$개 있다. 스위치 하나를 누르면 어떤 외양간 문은 열리고 어떤 문은 닫히며 나머지 문은 그대로다. 스위치가 이미 열린 문을 열려고 하거나 이미 닫힌 문을 닫으려고 하면 그 문의 상태는 바뀌지 않는다.

미르코는 원하는 스위치를 원하는 순서로 모두 누른다. 그런 다음 걸어서 닫혀 있는 외양간(저녁이라면 열려 있는 외양간)을 모두 찾아가 손으로 원하는 상태로 바꾸고, 마지막에 집으로 돌아온다. 미르코는 아침과 저녁 모두 걷는 거리를 최소로 하고 싶다.

외양간의 위치는 미르코의 집에서 떨어진 거리(미터)로 주어진다. 음수는 집 왼쪽에 있는 외양간을, 양수는 집 오른쪽에 있는 외양간을 뜻한다. 예를 들어 1번 외양간이 $-2$, 2번 외양간이 $3$, 3번 외양간이 $4$, 4번 외양간이 $10$에 있고 스위치가 다음과 같다고 하자.

아침에는 2번 스위치를 눌러 4번 외양간을 열고 나머지 외양간은 걸어서 여는 것이 가장 좋다. 이때 걷는 거리는 2(1번 외양간까지) + 5(1번에서 2번까지) + 1(2번에서 3번까지) + 4(3번에서 집까지) = 12미터다. 저녁에는 2번 스위치를 누른 다음 1번 스위치를 누르는 것이 가장 좋고, 그러면 1번 외양간만 열린 채로 남는다. 이 문까지 닫으려면 미르코는 2 + 2 = 4미터를 걸어야 한다.

외양간의 위치와 각 스위치가 어떤 외양간을 열고 닫는지가 주어질 때, 미르코가 아침과 저녁에 걸어야 하는 최소 거리를 각각 구하는 프로그램을 작성하시오.

첫째 줄에 외양간의 수 $N$ ($1 \le N \le 500$)과 스위치의 수 $M$ ($1 \le M \le 20\,000$)이 주어진다. 둘째 줄에는 외양간의 위치를 나타내는 정수 $X_i$ ($1 \le |X_i| \le 1\,000\,000$) $N$개가 오름차순으로 주어진다.

셋째 줄에는 규칙의 수 $G$ ($0 \le G \le 20\,000$)가 주어진다. 규칙 하나는 어떤 스위치를 눌렀을 때 어떤 외양간 문에 일어나는 동작을 정한다. 다음 $G$개 줄에는 규칙이 P V T 형식으로 한 줄에 하나씩 주어진다 ($1 \le P \le M$, $1 \le V \le N$). $P$는 스위치 번호, $V$는 외양간 번호이고, $T$는 otvara(연다)와 zatvara(닫는다) 중 하나로 $P$번 스위치를 눌렀을 때 $V$번 외양간 문에 일어나는 동작이다.

같은 위치에 있는 외양간은 없다. 순서쌍 $(P, V)$가 같은 규칙은 두 번 이상 주어지지 않는다.

첫째 줄에 미르코가 아침에 걸어야 하는 최소 거리를, 둘째 줄에 저녁에 걸어야 하는 최소 거리를 출력한다.

첫 번째 예제는 문제 본문의 예시와 같다.