Tetrahedron Rolling

A regular tetrahedron has 4 faces (all equilateral triangles). Initially the face marked A is placed on the ground. The tetrahedron may roll in three directions – to the left (L), to the right (R) and to the back (B). Its rolling path is described by a string composed only of the characters L, R and B.

The tetrahedron starts at time 1 with face A on the bottom. At the end of the first second the first instruction is executed, at the end of the second second the second instruction is executed, and so on. Note that after executing all instructions, one extra second passes with the tetrahedron in the final orientation. Thus, if there are n instructions, there are n+1 seconds in total, with the state at second i equal to the orientation after i-1 moves.

The rolling mechanism is simulated as follows. A tetrahedron orientation is represented by a triple \((b,f,r)\), where b is the face on the bottom, f is the face at the front and r is the face on the right. The only faces are A, B, C and D. For any valid state \((b,f,r)\) the remaining face \(T\) is determined by \[ T = \{A,B,C,D\} \setminus \{b,f,r\}. \] We define the following transformations (all formulas are given in \(\LaTeX\) format):

• For a left roll, define \[ f_{L}(b,f,r) = \Bigl(r,\,f,\,T\Bigr). \]
• For a right roll, define \[ f_{R}(b,f,r) = \Bigl(T,\,b,\,r\Bigr). \]
• For a back roll, define \[ f_{B}(b,f,r) = \Bigl(T,\,f,\,b\Bigr). \]

Thus, for example, if the initial state is \((A,B,C)\) (so that \(T=D\)), then

• \(f_{L}(A,B,C) = (C,B,D)\);
• \(f_{R}(A,B,C) = (D,A,C)\);
• \(f_{B}(A,B,C) = (D,B,A)\).

A key observation is that each move type is a 3-cycle on the three faces involved. For example, applying the left move three times, starting from \((A,B,C)\), we obtain the cycle

[ (A,B,C) \stackrel{L}{\longrightarrow} (C,B,D) \stackrel{L}{\longrightarrow} (D,B,A) \stackrel{L}{\longrightarrow} (A,B,C). ]

The problem has two types of operations. Initially a string of move instructions is given. Then there are two kinds of operations:

1. Query: Given two numbers \(L\) and \(R\), answer how many seconds in the time interval from \(L\) to \(R\) (inclusive) have the tetrahedron with face A on the bottom.
2. Update: Change the \(i\)th instruction to another move (L, R, or B).

For example, consider the instruction string LLLLB. The tetrahedron is in the following orientations (states are listed as (b,f,r)) at seconds 1 through 6:

Second 1: (A, B, C)   [A is bottom]
Second 2: (C, B, D)
Second 3: (D, B, A)
Second 4: (A, B, C)   [A is bottom]
Second 5: (C, B, D)
Second 6: (A, B, C)   [A is bottom]

Thus, a query for seconds 3 to 6 should report 2. After an update that changes the 3rd instruction to R (making the string LLRLB), the tetrahedron is in state A (bottom) only at seconds 1 and 5.

---

Input Format

The input begins with a line containing a nonempty string composed solely of the characters L, R and B (the initial move instructions). The next line contains an integer \(Q\) representing the number of operations. Each of the following \(Q\) lines is in one of the following two formats:

• Q L R — a query asking for the number of seconds between the \(L\)th and \(R\)th second (inclusive) during which face A is on the bottom.
• U i c — an update operation changing the \(i\)th instruction (1-indexed) to the character c (which is one of L, R, B).

Output Format

For each query operation, output the corresponding answer on a separate line.

Note: It is recommended that you use fast input/output methods due to the large size of the input.

inputFormat

The first line contains a nonempty string that represents the initial move instructions (each character is either L, R, or B).

The second line contains an integer \(Q\), the number of operations.

Each of the next \(Q\) lines contains an operation in one of the following formats:

• Q L R where 1 \(\le\) L \(\le\) R \(\le\) n+1, where \(n\) is the length of the instruction string
• U i c where 1 \(\le\) i \(\le\) n and c is one of L, R, B.

outputFormat

For each query operation, output a single integer on a separate line indicating the number of seconds in the given interval during which face A is on the bottom.

sample

LLLLB
3
Q 3 6
U 3 R
Q 1 6

2
2