410172: GYM103967 H Портальная пушка

H. Портальная пушкаограничение по времени на тест4 секундыограничение по памяти на тест1024 мегабайтавводстандартный вводвыводстандартный вывод

Рик прекрасно знает, что Морти нельзя доверять портальную пушку, но в последнее время Морти так надоел ему просьбами подарить ему собственную портальную пушку, что Рик сдался и сделал ему мини-версию.

Однако, чтобы Морти при этом как-то развивался (или просто чтобы ему было сложнее ее использовать), Рик сделал ее устройство достаточно запутанным. Всего на портальной пушке Морти есть $$$n$$$ параметров, каждый из которых может принимать значения от 'a' до 'z'. Обозначим параметр под номером $$$i$$$ за $$$p_i$$$.

За одно действие Морти может:

• выбрать произвольный номер параметра $$$i$$$ от $$$1$$$ до $$$n$$$ и изменить его значение на произвольное другое $$$c$$$ от 'a' до 'z';
• выбрать два возможных значения $$$c_1$$$ и $$$c_2$$$ от 'a' до 'z' и заменить значение у всех параметров, текущее значение которых равно $$$c_1$$$, на $$$c_2$$$;
• проверить, можно ли создать порталы в локациях с идентификаторами $$$(l_1, r_1)$$$ и $$$(l_2, r_2)$$$ (где $$$l_1 \leqslant r_1$$$ и $$$l_2 \leqslant r_2$$$) — для этого набор параметров на позициях $$$[l_1, r_1]$$$ должен поэлементно совпадать с набором параметров на позициях $$$[l_2, r_2]$$$, то есть должно выполняться $$$$$$\begin{cases} r_1 - l_1 = r_2 - l_2 \\ p_{l_1 + i} = p_{l_2 + i} & \text{для всех } 0 \leqslant i \leqslant r_1 - l_1 \end{cases}\text{.}$$$$$$

Поскольку Морти не шибко умный, ему сложно быстро проверять наборы параметров на равенство, а случайно сломать портальную пушку не хотелось бы. Помогите ему для каждого действия третьего типа понять, может ли он создать порталы в желаемых локациях, или нет.

Входные данные

В первой строке ввода дана строка $$$p$$$ длины $$$n$$$, состоящая из маленьких латинских букв — изначальные значения параметров пушки ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$).

В следующей строке дано единственное целое число $$$q$$$ — количество действий, которые совершает Морти ($$$1 \leqslant q \leqslant 2 \cdot 10^5$$$).

В следующих $$$q$$$ строках перечислены описания действий:

• «1 $$$i$$$ $$$c$$$» — присвоить $$$i$$$-му параметру значение $$$c$$$ ($$$1 \leqslant i \leqslant n$$$; $$$\text{'\t{a}'} \leqslant c \leqslant \text{'\t{z}'}$$$);
• «2 $$$c_1$$$ $$$c_2$$$» — заменить все значения всех параметров, равных $$$c_1$$$, на $$$c_2$$$ ($$$\text{'\t{a}'} \leqslant c_1, c_2 \leqslant \text{'\t{z}'}$$$);
• «3 $$$l_1$$$ $$$r_1$$$ $$$l_2$$$ $$$r_2$$$» — проверить возможность создания порталов в локациях $$$(l_1, r_1)$$$ и $$$(l_2, r_2)$$$ ($$$1 \leqslant l_1, r_1, l_2, r_2 \leqslant n$$$; $$$l_1 \leqslant r_1$$$; $$$l_2 \leqslant r_2$$$).

Выходные данные

На каждое действие третьего типа выведите в отдельной строке «YES» (без кавычек), если Морти может его выполнить, и «NO» иначе.

ПримерыВходные данные

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

Выходные данные

YES
YES
NO

Входные данные

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

Выходные данные

YES
YES
YES
YES