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$ 回処理せよ。

• 時刻 $0$ にバス停 $x_k$ を出発し、バス停 $y_k$ までバスのみを利用して移動するときの、所要時間の最小値を求めよ。

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

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

• $3 \leq N \leq 10^5 $
• $1 \leq M \leq 10^5 $
• $1 \leq Q \leq 10^5 $
• $ 1 \leq d_i \leq 10^2 \ (1 \leq i \leq N) $
• $ c_j = 'R' \ or \ 'L' \ (1 \leq j \leq M) $
• $ 1 \leq b_j \leq N \ (1 \leq j \leq M) $
• $ 1 \leq t_j \leq 10^5 \ (1 \leq j \leq M) $
• $ 1 \leq x_k, y_k \leq N \ (1 \leq k \leq Q) $
• $ x_k \neq y_k \ (1 \leq k \leq Q) $
• 入力で与えられる数はすべて整数
  

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

---