Problem Description

A regular tetrahedron has four faces, each of which is an equilateral triangle. Now, one of its faces is marked with the letter A, as shown in Figure 3, with A on the bottom face:

A regular tetrahedron can roll in three directions: left (L), right (R), and back (B). As shown in Figure 4:

Thus, the rolling process of the tetrahedron can be described using a string consisting only of the characters "L", "R", and "B".

Initially, the tetrahedron's A face is facing down. Now, SECSA will give this tetrahedron a sequence of rolling instructions—which is such a string—making the tetrahedron roll once per second. That is, at the beginning of the 1st second, the A face is down, and at the end of the 1st second, the first instruction is executed, and so on, until the entire instruction string is completed.

Your task is to tell SECSA how many seconds the A face of the tetrahedron is facing the ground between the L-th and R-th seconds when he inquires.

Since SECSA may not be satisfied with the rolling path of the tetrahedron and may modify a certain instruction at any time, your program should be able to perform the following two operations:

(1) Accept information from SECSA to modify the i-th instruction.

(2) Answer SECSA's query about how many seconds the A face is facing the ground between the L-th and R-th seconds.

For example, if the original instruction string is "LLLLB", then the A face is down at the 1st, 4th, and 6th seconds. If SECSA asks you about the situation from the 3rd to the 6th seconds, you should answer "2". If SECSA modifies the 3rd instruction to "R", the instruction string becomes "LLRLB", and then the A face is only down at the 1st and 5th seconds. As shown in Figure 5:

Input Format

The first line of the input file is an integer n, indicating the number of instructions in the instruction string.

The second line is a string containing n characters, each being one of "L", "R", or "B", representing the initial instruction string.

The third line is an integer m, indicating the total number of operations your program needs to process.

The next m lines, each describing an operation, are in one of the following two formats:

(1) 0 i c: Indicates changing the i-th instruction to c, where c is one of "L", "R", or "B".

(2) 1 L R: Indicates querying how many seconds the A face is down between the L-th and R-th seconds.

The input file guarantees: 1 <= i <= n, 1 <= L <= R <= n+1.

Output Format

For each query operation, the output file should sequentially output the answers provided by your program, with each answer being an integer, occupying one line.

Sample Input and Output

Sample Input #1

5
LLLLB
3
1 3 6
0 3 R
1 3 6

Sample Output #1

2
1

Sample Input #2

8
LLLLBRRR
7
1 1 9
1 4 7
0 2 R
1 1 9
1 2 9
0 7 B
1 3 5

Sample Output #2

4
2
1
0
0

Notes

The first sample is the example described in the problem.

In the second sample, according to the original instructions "LLLLBRRR", the A face is down at the 1st, 4th, 6th, and 9th seconds; after the first modification to "LRLLBRRR", only the A face at the 1st second is down; after the second modification to "LRLLBRBR", the A face is down at the 1st and 9th seconds.

1 <= n <= 60000

1 <= m <= 150000

见题面 Input 部分

见题面 Output 部分