JOI Machine Simulation

Bitaro received a JOI machine as a birthday present. The machine consists of a ball, N light tiles numbered from 1 to N, and M buttons. At power on, tile i emits light of color \(C_i\) which is either blue (B) or red (R). Each button j is associated with a light tile A_j.

When Button \(j\) is pushed, the following happens:

1. The ball is placed on tile \(A_j\).
2. Tile \(A_j\) immediately becomes red.
3. Then, the machine processes the ball repeatedly until it is removed. Let \(p\) be the current tile index where the ball is located. The operations are as follows:
   • If tile \(p\) is blue, it is changed to red. Afterwards, if \(p = 1\), the ball is removed; otherwise, the ball moves to tile \(p - 1\).
   • If tile \(p\) is red, it is changed to blue. Afterwards, if \(p = N\), the ball is removed; otherwise, the ball moves to tile \(p + 1\).

Bitaro performs Q experiments. In the \(k\)-th experiment, after turning on the machine (which resets the tiles to their initial colors \(C_1, C_2, \dots, C_N\)), he pushes buttons \(L_k, L_{k+1}, \dots, R_k\) sequentially. After each button press, he waits until the ball is removed before pushing the next button. Your task is to determine, for each experiment, the number of tiles that are red when the experiment finishes.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains three integers \(N\), \(M\) and \(Q\) which represent the number of tiles, the number of buttons, and the number of experiments respectively.

The second line contains a string of length \(N\) consisting only of the characters 'B' and 'R', representing the initial color of each light tile.

The third line contains \(M\) integers \(A_1, A_2, \dots, A_M\) where \(A_j\) is the tile number associated with the \(j\)-th button.

Then \(Q\) lines follow. The \(k\)-th line contains two integers \(L_k\) and \(R_k\), indicating that in the \(k\)-th experiment, Bitaro pushes buttons \(L_k, L_{k+1}, \dots, R_k\) in that order.

outputFormat

Output \(Q\) lines. The \(k\)-th line should contain a single integer representing the number of red tiles after the \(k\)-th experiment finishes.

sample

5 5 3
BRBRB
3 1 5 4 2
1 1
1 3
2 5

0
2
4