Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×
H. String Mutation
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You have string $$$p$$$ of length $$$n$$$, each of its characters is from 'a' to 'z', i.e. a lowercase Latin letter.

In one action you can:

  • choose any number $$$i$$$ from $$$1$$$ to $$$n$$$ and change the value of $$$p_i$$$ to any other $$$c$$$ from 'a' to 'z';
  • choose two possible values $$$c_1$$$ and $$$c_2$$$ from 'a' to 'z' and replace the value of all characters equal to $$$c_1$$$ with $$$c_2$$$;
  • check if strings formed by the characters of the string on positions from $$$l_1$$$ to $$$r_1$$$ and from $$$l_2$$$ to $$$r_2$$$ (where $$$l_1 \leq r_1$$$ and $$$l_2 \leq r_2$$$) are equal; i.e. that the following holds: $$$$$$\begin{cases} r_1 - l_1 = r_2 - l_2 \\ p_{l_1 + i} = p_{l_2 + i} & \text{for all } 0 \leq i \leq r_1 - l_1 \end{cases}\text{.}$$$$$$

Determine for each query of the third type whether the corresponding strings are equal or not.

Input

The first line of input contains a string $$$p$$$ of length $$$n$$$, consisting of lowercase Latin letters — the initial characters ($$$1 \leq n \leq 2 \cdot 10^5$$$).

The next line contains a single integer $$$q$$$ — the number of actions that will be performed ($$$1 \leq q \leq 2 \cdot 10^5$$$).

In the following $$$q$$$ lines, the descriptions of the queries are listed in the form:

  • "1 $$$i$$$ $$$c$$$" — assign the value $$$c$$$ to the $$$i$$$-th character of the string ($$$1 \leq i \leq n$$$; $$$\text{'\t{a}'} \leq c \leq \text{'\t{z}'}$$$);
  • "2 $$$c_1$$$ $$$c_2$$$" — replace all values of all characters in the string equal to $$$c_1$$$ with $$$c_2$$$ ($$$\text{'\t{a}'} \leq c_1, c_2 \leq \text{'\t{z}'}$$$);
  • "3 $$$l_1$$$ $$$r_1$$$ $$$l_2$$$ $$$r_2$$$" — check that substrings formed by segments $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ are equal ($$$1 \leq l_1, r_1, l_2, r_2 \leq n$$$; $$$l_1 \leq r_1$$$; $$$l_2 \leq r_2$$$).
Output

For each query of the third type, output on a separate line a string "YES" (without quotes) if corresponding substrings are equal, and "NO" otherwise.

Examples
Input
aaabc
6
3 1 2 2 3
1 4 c
2 c a
3 1 4 2 5
1 3 x
3 1 4 2 5
Output
YES
YES
NO
Input
abracadabra
7
3 1 4 8 11
1 7 r
2 a c
2 b c
3 1 4 8 11
3 1 4 5 8
3 2 4 6 8
Output
YES
YES
YES
YES