Given a string $S$ consisting only of lowercase letters, there are $Q$ operations of the following two types:

• 1 i c: Change $S_i$ to $c$ ($1\le i\le |S|$, $c$ is a lowercase letter).
• 2 l r: Query the number of palindromic suffixes of $S[l...r]$ ($1\le l\le r\le |S|$).

Input

The first line contains a string $S$ consisting only of lowercase letters ($|S|\le 2\times 10^5$).

The second line contains an integer $Q$ ($Q\le 2\times 10^5$), representing the number of operations.

The next $Q$ lines each contain an operation.

This problem is forced online. For operation $1$, the input $i$ must be XORed with $lastans$. For operation $2$, both $l$ and $r$ must be XORed with $lastans$. $lastans$ is the answer to the previous operation $2$. If there is no previous operation $2$, then $lastans=0$.

Output

For each operation $2$, output the answer on a new line.

Examples

Input 1

abbbaabbba
7
2 10 10
1 9 a
1 11 b
2 6 9
1 9 a
1 6 a
2 2 6

Output 1

1
1
3

The decrypted input is:

abbbaabbba
7
2 10 10
1 8 a
1 10 b
2 7 8
1 8 a
1 7 a
2 3 7

For the 1st operation, the query string is: a, the palindromic suffix is a.

For the 4th operation, the query string is: ba, the palindromic suffix is a.

For the 7th operation, the query string is: bbaaa, the palindromic suffixes are a, aa, and aaa.

Input 2

abaabaabbaabbaabaaba
10
2 15 19
2 8 18
2 6 15
2 14 13
2 8 15
2 1 16
2 14 21
2 9 12
2 4 17
2 5 12

Output 2

2
2
3
1
2
4
2
2
3
4

The decrypted input is:

abaabaabbaabbaabaaba
10
2 15 19
2 10 16
2 4 13
2 13 14
2 9 14
2 3 18
2 10 17
2 11 14
2 6 19
2 6 15

Constraints

For all data, $1\le |S|,Q\le 2\times 10^5$.

The detailed subtask constraints and scores are as follows: