Problem F: Bus

Problem

円環状に $1$ から $N$ までの番号がつけられた $N$ 個のバス停が右回りに並んでいる。 隣接するバス停どうしは道で結ばれている。 各 $i \ (1 \le i \le N)$ について、バス停 $i$ とバス停 $i+1$ の間を直接結ぶ道の長さは $d_i$ メートルである。 ただし、バス停 $N+1$ はバス停 $1$ のことを表す。

$M$ 台のバスがある。 $j \ (1 \le j \le M)$ 番目のバスは $c_j='R'$ のとき右回り、$c_j='L'$ のとき左回りに走行する。 また、時刻 $0$ にバス停 $b_j$ を出発し、$1$ メートル進むのに $t_j$ 秒かかる。

この問題において、

とする。

以下のクエリを合計 $Q$ 回処理せよ。

Input

入力は以下の形式で与えられる。

$N$ $M$ $Q$
$d_1$ $\ldots$ $d_N$
$c_1$ $b_1$ $t_1$
$\vdots$
$c_M$ $b_M$ $t_M$
$x_1$ $y_1$
$\vdots$
$x_Q$ $y_Q$

1行目にバス停の数 $N$、バスの数 $M$、クエリの数 $Q$ が空白区切りで与えられる。
2行目に隣接するバス停を繋ぐ道の情報が空白区切りで与えられる。
3行目から続く $M$ 行にバスの情報が空白区切りで与えられる。
続く $Q$ 行にクエリの情報が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

Output

出力は $Q$ 行からなる。
各クエリに対し、所要時間の最小値を出力せよ。
$k$ 行目には $k$ 番目のクエリに対する答えを出力せよ。

Sample Input 1

3 1 6
1 2 3
R 1 1
1 2
1 3
2 1
2 3
3 1
3 2

Sample Output 1

1
3
6
3
6
7

$1$ つ目のクエリでは、時刻 $0$ にバス停 $1$ からバス $1$ に乗り、時刻 $1$ にバス停 $2$ で降りるのが最適である。

Sample Input 2

4 6 7
45 72 81 47
R 1 47202
L 1 2156
L 2 95728
R 1 30739
L 3 39679
L 4 86568
3 2
3 4
1 2
2 4
4 3
1 4
2 1

Sample Output 2

431200
629552
431200
629552
275968
101332
528220