Dynamic LCQ Query

Given a string S, you need to process Q operations. The string supports the following operations:

• LCQ Query: Q x y. Compute the function \( LCQ(x, y) \), which is defined as the length of the longest common prefix between the suffix of S starting at position \(x\) and the suffix starting at position \(y\). Positions are 1-indexed.
• Update Query: C pos ch. Change the character at position \(pos\) of the string to character ch.
• Insertion Query: I pos ch. Insert character ch at position \(pos\) (inserting before the current character at that position). If \(pos = |S|+1\), then ch is appended at the end.

For example, consider the string "madamimadam" with 1-indexed positions as follows:

Index:   1 2 3 4 5 6 7 8 9 10 11
Char:    m a d a m i m a d  a  m

According to the definition, we have:

\( LCQ(1, 7) = 5 \), \( LCQ(2, 10) = 1 \), and \( LCQ(4, 7) = 0 \).

Your task is to implement these operations. Note that the string changes over time due to the update and insertion queries, and the LCQ queries should always be answered based on the current state of the string.

inputFormat

The input begins with a line containing the initial string S (consisting of lowercase letters).

The second line contains a single integer Q representing the number of queries.

Each of the next Q lines contains one query in one of the following formats:

• Q x y: Query the longest common prefix of the suffix starting at position x and the suffix starting at position y.
• C pos ch: Change the character at position pos to ch.
• I pos ch: Insert character ch at position pos (inserting before the character originally at that position; if \(pos = |S|+1\), append at the end).

It is guaranteed that the given operations are valid and positions are 1-indexed.

outputFormat

For each query of the form Q x y, output a single line containing the value of \( LCQ(x, y) \), which is the length of the longest common prefix of the two corresponding suffixes of S.

sample

madamimadam
3
Q 1 7
Q 2 10
Q 4 7

5
1
0

</p>