Description

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

In one roll, a regular tetrahedron clearly has 3 possible directions: left (L), right (R), and back (B). As shown in Figure 4:

Therefore, the rolling process of this tetrahedron can be described by a string containing only “L”, “R”, and “B”.

Initially, face A of the tetrahedron faces downward. Now SECSA will give this tetrahedron a sequence of rolling instructions—of course, such a string—and make the tetrahedron roll once per second. That is, during the 1st second, face A faces downward; at the end of the 1st second the first instruction is executed; at the end of the 2nd second the second instruction is executed; and so on, until the whole instruction string is executed.

Your task is: when SECSA asks you, tell him how many seconds, from the L-th second to the R-th second, face A is facing the ground.

Of course, SECSA may be dissatisfied with the rolling path of this tetrahedron, and he may modify any one instruction at any time. Therefore, your program should be able to perform the following two operations:

(1) Accept SECSA’s modification of the i-th instruction.

(2) Answer SECSA’s query: “From the L-th second to the R-th second, how many seconds is face A facing the ground?”

For example, suppose the original instruction string is “LLLLB”. Then during the 1st, 4th, and 6th seconds, face A is facing downward. At this time, if SECSA asks about the 3rd second to the 6th second, you should answer “2”. If SECSA changes the 3rd instruction to “R”, the instruction string becomes “LLRLB”, and then the tetrahedron is facing downward only during 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 character is one of “L”, “R”, and “B”, representing the initial instruction string.

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

In the next $m$ lines, each line describes an operation in one of the following two formats:

(1) 0 i c: Change the $i$-th instruction to $c$, where $c$ is one of “L”, “R”, and “B”.

(2) 1 L R: Query how many seconds, from the $L$-th second to the $R$-th second, face A is facing downward.

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

Output Format

For each query operation, output your program’s answer in order. Each answer is an integer, one per line.

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

2
1

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

4
2
1
0
0

Hint

The first sample is the example in the problem description.

In the second sample, with the original instructions “LLLLBRRR”, face A faces downward during the 1st, 4th, 6th, and 9th seconds. After the first modification, the instructions become “LRLLBRRR”, and then face A faces downward only during the 1st second. After the second modification, the instructions become “LRLLBRBR”, and then face A faces downward during the 1st and 9th seconds.

Constraints:

$1<=n<=60000$

$1<=m<=150000$

Translated by ChatGPT 5