円環状に $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$ 回処理せよ。
入力は以下の形式で与えられる。
$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$ 行にクエリの情報が空白区切りで与えられる。
入力は以下の条件を満たす。
出力は $Q$ 行からなる。
各クエリに対し、所要時間の最小値を出力せよ。
$k$ 行目には $k$ 番目のクエリに対する答えを出力せよ。
3 1 6 1 2 3 R 1 1 1 2 1 3 2 1 2 3 3 1 3 2
1 3 6 3 6 7
$1$ つ目のクエリでは、時刻 $0$ にバス停 $1$ からバス $1$ に乗り、時刻 $1$ にバス停 $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
431200 629552 431200 629552 275968 101332 528220