E. Palindrome Query
time limit per test
4 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

De Prezer loves palindrome strings. A string s1s2...sn is palindrome if and only if it is equal to its reverse.

De Prezer also loves queries.

You are given string s of length n and m queries. There are 3 types of queries :

1. 1 p x : Modify sp = x where 1 ≤ p ≤ n and x is a lower case English letter.

2. 2 p : Print the length of the largest palindrome substring of s like slsl + 1...sr such that l ≤ p ≤ r and r - p = p - l. (1 ≤ p ≤ n)

3. 3 p : Print the length of the largest palindrome substring of s like slsl + 1...sr such that l ≤ p and p + 1 ≤ r and r - p - 1 = p - l. (1 ≤ p ≤ n - 1) or  - 1 if there is no such substring.

Input

The first line of input contains s and m.

Next m lines contain queries.

1 ≤ n, m ≤ 105

s only contains lower case English letters.

Output

For each query of type 2 and 3 print the answer in a single line.

Examples
Input
abcd 3
3 1
1 2 c
3 2
Output
-1
2
Input
abcba 6
2 3
1 3 b
2 3
3 2
1 1 b
3 2
Output
5
5
2
4