题目描述

In this problem we consider three types of operations that can be applied to any 0-based string $t$ of length $|t| \ge 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 \le 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(\text{“pda”}) = \text{“adp”}$, $R(\text{“pda”}, 2) = \text{“dap”}$, and $L(\text{“pda”}, 2) = \text{“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, \dots, F_K$. Your task is to find out how many pairs of indices $(i, j)$ there are such that $1 \le i \le j \le K$, and applying the sublist of operations $F_i, F_{i+1}, \dots, F_j$ to $S$ yields $S$ as the final result.

Consider for instance $S = \text{“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(\text{“pda”}, 2) = \text{“dap”}$, which is different from $S$. The result of applying the sublist $F_1, F_2$ to $S$ is $L(R(\text{“pda”}, 2), 2) = L(\text{“dap”}, 2) = \text{“pda”} = S$. Finally, the result of applying the sublist $F_2$ to $S$ is $L(\text{“pda”}, 2) = \text{“apd”}$, which is different from $S$. Thus, in this example the answer is 1.

输入格式

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

The second line contains an integer $K$ ($1 \le K \le 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 a single line with an integer indicating the requested number of pairs.

pda
2
R 2
L 2

1

aaa
4
R 1
I
I
R 1

10

caso
6
L 1
I
I
R 1
I
I

4