H. Harmonic Operations
time limit per test
0.4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In this problem, we consider three types of operations that can be applied to any $$$0$$$-based string $$$t$$$ of length $$$|t| \geq 2$$$.

  • $$$I(t)$$$: Reverses $$$t$$$.
  • $$$R(t,D)$$$: Rotates $$$t$$$ to the right $$$D$$$ positions, for some positive integer $$$D<|t|$$$. That is, for each $$$0 \leq i < |t|$$$, the character at position $$$(i + D) \bmod |t|$$$ in $$$R(t,D)$$$ is the character at position $$$i$$$ in $$$t$$$.
  • $$$L(t,D)$$$: Analogous to $$$R(t,D)$$$, but rotates $$$t$$$ to the left instead of to the right.
For example, $$$I("\texttt{pda}")="\texttt{adp}"$$$, $$$R("\texttt{pda}",2)="\texttt{dap}"$$$, and $$$L("\texttt{pda}",2)="\texttt{apd}"$$$. Note that for any $$$t$$$ and any $$$D$$$, it holds that $$$|I(t)|=|R(t,D)|=|L(t,D)|=|t|$$$.

When a list of the above operations is applied to a string, it is done sequentially in list order. That is, the first operation of the list is applied to the original string, the second operation is applied to the result after having applied the first operation, the third operation is applied to the result after having applied the first two operations, and so on.

You are given a string $$$S$$$ consisting of lowercase letters, and a list of $$$K$$$ operations $$${F_1}, {F_2}, \ldots, {F_K}$$$. Your task is to find out how many pairs of indices $$$(i,j)$$$ there are such that $$$1 \leq i \leq j \leq K$$$, and applying the sublist of operations $$${F_i}, {F_{i+1}}, \ldots, {F_j}$$$ to $$$S$$$ yields $$$S$$$ as the final result.

Consider, for instance, $$$S="\texttt{pda}"$$$, $$$K=2$$$, $$$F_1=R(t,2)$$$ and $$$F_2=L(t,2)$$$. The result of applying the sublist $$$F_1$$$ to $$$S$$$ is $$$R("\texttt{pda}",2)="\texttt{dap}"$$$, which is different from $$$S$$$. The result of applying the sublist $$$F_1, F_2$$$ to $$$S$$$ is $$$L(R("\texttt{pda}",2),2)=L("\texttt{dap}",2)="\texttt{pda}"=S$$$. Finally, the result of applying the sublist $$$F_2$$$ to $$$S$$$ is $$$L("\texttt{pda}",2)="\texttt{apd}"$$$, which is different from $$$S$$$. Thus, in this example, the answer is $$$1$$$.

Input

The first line contains a string $$$S$$$ ($$$2 \leq |S| \leq 2 \cdot 10^5$$$) which is made up of lowercase letters.

The second line contains an integer $$$K$$$ ($$$1 \leq K \leq 2 \cdot 10^5$$$) indicating the number of operations in the list of operations that is being considered.

Operations are described in the next $$$K$$$ lines, in the order they appear in the list, one operation per line. If the operation is $$$I(t)$$$, the line contains the uppercase letter "I". If the operation is $$$R(t,D)$$$, the line contains the uppercase letter "R" and the integer $$$D$$$ ($$$1 \le D < |S|$$$). Finally, if the operation is $$$L(t,D)$$$, the line contains the uppercase letter "L" and the integer $$$D$$$ ($$$1 \le D < |S|$$$).

Output

Output a single line with an integer indicating the requested number of pairs.

Examples
Input
pda
2
R 2
L 2
Output
1
Input
aaa
4
R 1
I
I
R 1
Output
10
Input
caso
6
L 1
I
I
R 1
I
I
Output
4