Problem Description

Martians have recently been studying an operation: finding the common prefix of two suffixes of a string.

For example, consider this string: madamimadam. We label its characters as follows:

序号 1 2 3 4 5 6 7 8 9 10 11 
字符 m a d a m i m a d a m

Now, Martians define a function $LCQ(x, y)$, which means: the length of the common prefix between the substring starting at the $x$-th character and the substring starting at the $y$-th character of the string. For example, $LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0$.

In the process of studying the $LCQ$ function, Martians found a connection: if you sort all suffixes of the string, you can quickly compute the value of $LCQ$; likewise, if you know the values of $LCQ$, you can quickly sort the suffixes of the string.

Although Martians cleverly discovered a fast algorithm for computing $LCQ$, the unyielding Earthlings posed a new challenge: while computing $LCQ$, the string itself may change. Specifically, you may change the value of a character in the string, or insert a character at some position in the string. The Earthlings want to test whether Martians can still compute $LCQ$ quickly under such a complex scenario.

Input Format

The first line gives the initial string. The second line is a non-negative integer $M$, the number of operations. The next M lines each describe one operation. There are 3 types of operations:

1. Query. Syntax: $Q$ $x$ $y$, where $x$, $y$ are positive integers. Function: compute $LCQ(x, y)$. Constraint: $1 \leq x, y \leq$ current string length.
2. Modify. Syntax: $R$ $x$ $d$, where $x$ is a positive integer and $d$ is a character. Function: replace the $x$-th character of the string with $d$. Constraint: $x$ does not exceed the current string length.
3. Insert. Syntax: $I$ $x$ $d$, where $x$ is a non-negative integer and $d$ is a character. Function: insert character $d$ after the $x$-th character of the string; if $x=0$, insert at the beginning of the string. Constraint: $x$ does not exceed the current string length.

Output Format

For each query operation in the input, output the corresponding answer, one per line.

madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

5
1
0
2
1

Hint

1. All strings always consist of lowercase letters only.
2. $M\leq150,000$
3. The string length $L$ always satisfies $L\leq100,000$.
4. The number of query operations does not exceed $10,000$.

For testdata 1 and 2, the string length never exceeds $1,000$. For testdata 3, 4, and 5, there are no insert operations.

Translated by ChatGPT 5