F. Настя и ПСП
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

  Настя, как и вы  — олимпиадный программист, но она только учится. Недавно Денис ей рассказал о способе проверки строки на то, что она является правильной скобочной последовательностью. После этого неожиданно Настя придумала более сложную задачу, которую Денис не смог решить, а сможете ли Вы?

Дана строка $$$s$$$, состоящая из $$$k$$$ видов пар скобок. Каждая скобка имеет вид $$$t$$$ — целое число, такое что $$$1 \leq |t| \leq k$$$. Если скобка имеет вид $$$t$$$, то:

  • Если $$$t > 0$$$, то это открывающая скобка типа $$$t$$$.
  • Если $$$t < 0$$$, то это закрывающая скобка типа $$$-t$$$.

Таким образом, всего существует $$$k$$$ типов пар скобок.

Требуется отвечать на следующие запросы:

  1. Заменить скобку на позиции $$$i$$$ на скобку вида $$$t$$$.
  2. Проверить, является ли подстрока с $$$l$$$-й по $$$r$$$-ю позиции, включительно, правильной скобочной последовательностью.

Напомним определение правильной скобочной последовательности:

  • Пустая последовательность является правильной.
  • Если $$$A$$$ и $$$B$$$ - две правильные скобочные последовательности, то их конкатенация «$$$A$$$ $$$B$$$» тоже является правильной скобочной последовательностью.
  • Если $$$A$$$ - правильная скобочная последовательность, $$$c$$$ $$$(1 \leq c \leq k)$$$  — некоторый тип скобок, то последовательность «$$$c$$$ $$$A$$$ $$$-c$$$» тоже является правильной.
Входные данные

В первой строке дано $$$n$$$ $$$(1 \leq n \leq 10^5)$$$  — длина строки и число $$$k$$$ $$$(1 \leq k \leq n)$$$  — количество типов скобок.

Во второй строке дана строка $$$s$$$ длиной $$$n$$$ символов  — $$$n$$$ целых чисел $$$s_1, s_2, \ldots, s_n$$$ $$$(1 \leq |s_i| \leq k)$$$.

В третьей строке дано число $$$q$$$ $$$(1 \leq q \leq 10^5)$$$  — количество запросов.

Каждая из следующих $$$q$$$ строк описывает запросы:

  • $$$1$$$ $$$i$$$ $$$t$$$ - запрос $$$1$$$-го типа $$$(1 \leq i \leq n, 1 \leq |t| \leq k)$$$.
  • $$$2$$$ $$$l$$$ $$$r$$$ - запрос $$$2$$$-го типа $$$(1 \leq l \leq r \leq n)$$$.
Выходные данные

Для каждого запроса $$$2$$$ типа выведите «Yes», если подстрока из запроса является правильной скобочной последовательностью и «No», иначе.

Вы можете выводить буквы в любом регистре.

Примеры
Входные данные
2 1
1 -1
1
2 1 2
Выходные данные
Yes
Входные данные
2 2
1 -2
1
2 1 2
Выходные данные
No
Входные данные
6 2
1 2 -2 -1 1 -1
3
2 1 6
2 1 4
2 2 5
Выходные данные
Yes
Yes
No
Входные данные
2 2
-1 1
4
2 1 2
1 1 1
1 2 -1
2 1 2
Выходные данные
No
Yes
Примечание

В четвёртом тесте изначально строка не является правильной скобочной последовательностью, значит ответ на первый вопрос «No». После двух изменений она имеет вид «$$$1$$$ $$$-1$$$», значит она стала правильной скобочной последовательностью и ответ на четвёртый запрос «Yes».