401906: GYM100570 E Palindrome Query

De Prezer loves palindrome strings. A string s₁s₂...s_n 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 s_p = 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 s_ls_l + 1...s_r 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 s_ls_l + 1...s_r 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.

The first line of input contains s and m.

Next m lines contain queries.

1 ≤ n, m ≤ 10⁵

s only contains lower case English letters.

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

abcd 3
3 1
1 2 c
3 2

-1
2

abcba 6
2 3
1 3 b
2 3
3 2
1 1 b
3 2

5
5
2
4