Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
109 - ZOJ Monthly, September 2011 - E
Gao the String I

Time Limit: 4 Seconds      Memory Limit: 262144 KB

Given a string S and a list of operations. You should finish the operations step by step. There are four kinds of operation described as below.

  1. Reverse a b : Reverse the substring which index is between a and b(inclusive, index is start from 1) in S.
  2. Modify p c : Modify the character whose index is p into c(c is a lowercase letter).
  3. Lcp a b : Output the length of the longest common prefix between suffix start from a and b.
  4. Palindrome : Output the longest palindromic substring of S.

For example:

  1. String "abcde" became "adcbe" after the operation "Reverse 2 4".
  2. String "abcde" became "abade" after the operation "Modify 3 a".
  3. The answer of "Lcp 2 4" should be 2 when the string is "cababc". The suffix start from 2 is "ababc". The suffix start from 4 is "abc". So the longest common prefix between them is "ab".
  4. The answer of "Palindrome" should be 6 when the string is "cabccbad".

Input

There are multiple test cases. The first line of each case is a string S indicating the initial string(1 ≤ |S| ≤ 100000 ). The following line contains an integer m ( 1 ≤ m ≤ 10000 ) indicating the amount of operations. Then, following m lines, one for an operation. Process to the end of file.

Notice that S only contains lowercase letters. By the way, the amount of "Palindrome" in each case will not exceed 10.

Output

One line for each "Lcp" or "Palindrome".

Sample Input

abaca
8
Lcp 1 3
Lcp 3 4
Palindrome
Reverse 4 5
Lcp 3 4
Reverse 4 5
Modify 4 b
Palindrome

Sample Output

1
0
3
1
5

Author: CHEN, Weijie
Submit    Status