Настя, как и вы — олимпиадный программист, но она только учится. Недавно Денис ей рассказал о способе проверки строки на то, что она является правильной скобочной последовательностью. После этого неожиданно Настя придумала более сложную задачу, которую Денис не смог решить, а сможете ли Вы?
Дана строка \(s\), состоящая из \(k\) видов пар скобок. Каждая скобка имеет вид \(t\) — целое число, такое что \(1 \leq |t| \leq k\). Если скобка имеет вид \(t\), то:
- Если \(t > 0\), то это открывающая скобка типа \(t\).
- Если \(t < 0\), то это закрывающая скобка типа \(-t\).
Таким образом, всего существует \(k\) типов пар скобок.
Требуется отвечать на следующие запросы:
- Заменить скобку на позиции \(i\) на скобку вида \(t\).
- Проверить, является ли подстрока с \(l\)-й по \(r\)-ю позиции, включительно, правильной скобочной последовательностью.
Напомним определение правильной скобочной последовательности:
- Пустая последовательность является правильной.
- Если \(A\) и \(B\) - две правильные скобочные последовательности, то их конкатенация «\(A\) \(B\)» тоже является правильной скобочной последовательностью.
- Если \(A\) - правильная скобочная последовательность, \(c\) \((1 \leq c \leq k)\) — некоторый тип скобок, то последовательность «\(c\) \(A\) \(-c\)» тоже является правильной.
Выходные данные
Для каждого запроса \(2\) типа выведите «Yes», если подстрока из запроса является правильной скобочной последовательностью и «No», иначе.
Вы можете выводить буквы в любом регистре.
Примечание
В четвёртом тесте изначально строка не является правильной скобочной последовательностью, значит ответ на первый вопрос «No». После двух изменений она имеет вид «\(1\) \(-1\)», значит она стала правильной скобочной последовательностью и ответ на четвёртый запрос «Yes».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
1 -1
1
2 1 2
|
Yes
|
|
2
|
2 2
1 -2
1
2 1 2
|
No
|
|
3
|
6 2
1 2 -2 -1 1 -1
3
2 1 6
2 1 4
2 2 5
|
Yes
Yes
No
|
|
4
|
2 2
-1 1
4
2 1 2
1 1 1
1 2 -1
2 1 2
|
No
Yes
|