Bus

Problem

There are $N$ bus stops clockwise, numbered from $1$ to $N$ in a circle. Adjacent bus stops are connected by a road. For each $i \ (1 \ le i \ le N)$, the length of the direct connection between the bus stop $i$ and the bus stop $i + 1$ is $d_i$ meters. However, bus stop $N + 1$ means bus stop $1$.

There are $M$ buses. The $j \ (1 \ le j \ le M)$ th bus runs clockwise when $c_j ='R'$ and counterclockwise when $c_j ='L'$. It also takes $t_j$ seconds to depart bus stop $b_j$ at time $0$ and travel $1$ meters.

In this matter

• The bus keeps running forever
• It doesn't take long to get on and off the bus
• At a bus stop, you can get on and off the bus the moment it passes the bus stop.
• You cannot get on and off the bus except at the bus stop
• You can take as many buses as you like

And.

Process the following query a total of $Q$ times.

• Find the minimum time required to depart bus stop $x_k$ at time $0$ and travel to bus stop $y_k$ using only the bus.

Constraints

The input satisfies the following conditions.

• $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)$
• All numbers given in the input are integers

Input

The input is given in the following format.

$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$

The number of bus stops $N$, the number of buses $M$, and the number of queries $Q$ are given on the first line, separated by blanks. Information on the road connecting the adjacent bus stops is given on the second line, separated by blanks. Bus information is given on the $M$ line starting from the third line, separated by blanks. Query information is given in the following $Q$ line, separated by blanks.

Output

The output consists of $Q$ lines. Output the minimum required time for each query. Print the answer to the $k$ th query on the $k$ line.

Examples

Input

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

Output

1 3 6 3 6 7

Input

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

Output

431200 629552 431200 629552 275968 101332 528220

inputFormat

input satisfies the following conditions.

• $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)$
• All numbers given in the input are integers

Input

The input is given in the following format.

$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$

The number of bus stops $N$, the number of buses $M$, and the number of queries $Q$ are given on the first line, separated by blanks. Information on the road connecting the adjacent bus stops is given on the second line, separated by blanks. Bus information is given on the $M$ line starting from the third line, separated by blanks. Query information is given in the following $Q$ line, separated by blanks.

outputFormat

Output

The output consists of $Q$ lines. Output the minimum required time for each query. Print the answer to the $k$ th query on the $k$ line.

Examples

Input

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

Output

1 3 6 3 6 7

Input

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

Output

431200 629552 431200 629552 275968 101332 528220

样例

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

</p>