Problem Description

$ N $ pieces of Othello are arranged in a straight line from left to right.
The colors of the pieces are represented by the string $ S $, where the $ i $-th character from the left in $ S $ corresponds to the $ i $-th piece from the left, with W indicating a white face and B indicating a black face.

The magician IOI placed $ M $ new pieces. The placement of the $ i $-th piece is determined by two values, $ D_i $ and $ F_i $:

• If $ D_i = $ L, the piece is placed slightly to the left of the leftmost piece; if $ D_i = $ R, it is placed slightly to the right of the rightmost piece.
• If $ F_i = $ W, the face of the piece is white; if $ F_i = $ B, the face is black.
• Immediately after placing a piece, all pieces sandwiched between the placed piece and the nearest same-colored piece are flipped!

However, JOI was unable to see this trick. To understand what the trick entailed, he asked $ Q $ questions. The $ i $-th question was, "What was the color of the $ P_i $-th piece from the left after the $ T_i $-th piece was placed?"

Answer all of JOI's questions for him.

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $ $ M $ $ D_1 $ $ F_1 $ $ D_2 $ $ F_2 $ : : $ D_M $ $ F_M $ $ Q $ $ T_1 $ $ P_1 $ $ T_2 $ $ P_2 $ : : $ T_Q $ $ P_Q $

Output Format

Output $ Q $ lines.

The $ i $-th line should contain the answer to the $ i $-th question.

Sample Input and Output

Sample Input #1

5
WWBBW
3
L B
R W
R B
2
1 2
3 4

Sample Output #1

B
B

Sample Input #2

1
B
5
L W
L B
R W
R W
L W
5
1 1
2 2
3 2
4 5
5 3

Sample Output #2

W
B
B
W
W

Notes/Hints

Constraints

• $ N $ is an integer between $ 1 $ and $ 150,000 $ inclusive.
• $ M $ is an integer between $ 1 $ and $ 150,000 $ inclusive.
• $ Q $ is an integer between $ 1 $ and $ 150,000 $ inclusive.
• $ S $ is a string of length $ N $ consisting only of W and B.
• $ D_i $ is either L or R.
• $ F_i $ is either W or B.
• $ T_i $ is an integer between $ 1 $ and $ M $ inclusive.
• After placing the $ T_i $-th piece, there are at least $ P_i $ pieces.
• All inputs except $ D_i $, $ F_i $, and $ S $ are integers.

Subtasks

Subtask $ 1 $ \[$ 25 $ points\]

• $N \leq 100$.
• $M \leq 100$.
• $Q \leq 100$.

Subtask $ 2 $ \[$ 29 $ points\]

• $ N = 1 $.

Subtask $ 3 $ \[$ 33 $ points\]

• $N \leq 100$.

Subtask $ 4 $ \[$ 13 $ points\]

• No additional constraints.

Sample Explanation 1

Initially, the pieces are colored WWBBW. After the 1st piece (B) is placed to the left, it becomes BWWBBW → BBBBBW. All pieces between the leftmost B and the 4th B from the left are flipped. After the 2nd piece (W) is placed to the right, it becomes BBBBBWW, but nothing is flipped. After the 3rd piece (B) is placed to the right, it becomes BBBBBWWB → BBBBBBBB. Then, answer JOI's questions: The 1st question asks about the 2nd piece after the 1st placement, which is B. The 2nd question asks about the 4th piece after the 3rd placement, which is B.

Sample Explanation 2

Initially, the piece is B, which changes to WB → BBB → BBBW → BBBWW → WWWWWW.

见题面 Input 部分

见题面 Output 部分