D. Прогулка по скобкам
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$ длины $$$n$$$, состоящая из символов '(' и ')'. Вы идете по этой строке. Вы начинаете с первого символа $$$s$$$ и хотите сделать последовательность шагов так, чтобы закончить на $$$n$$$-м символе. За один шаг вы можете переместиться на один символ влево (если вы стоите не на первом символе) или на один символ вправо (если вы стоите не на последнем символе). Вы не можете оставаться на одном и том же месте, однако вы можете посетить любой символ, включая первый и последний, любое количество раз.

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

Правильная скобочная последовательность — это последовательность скобок, которая может быть преобразована в правильное арифметическое выражение путем добавления символов '1' и '+' между исходными символами последовательности. Например, последовательности скобок «()()», «(())» являются правильными ( итоговыми выражениями являются: «(1)+(1)», «((1+1)+1)»), а последовательности «)(» и «(» не являются правильными.

Один возможный корректный путь по $$$s=\mathtt{(())()))}$$$. Красная точка указывает на ваше текущее положение, а красная строка — на записанную вами строку. Обратите внимание, что итоговая красная строка — это правильная скобочная последовательность.

Вам даны $$$q$$$ запросов. Каждый запрос меняет значение символа с '(' на ')' или наоборот. После каждого изменения определите, является ли данная строка проходимой.

Запросы сохраняются, то есть эффект от каждого запроса распространяется на последующие запросы.

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2\cdot 10^5$$$) — размер строки и количество запросов, соответственно.

Вторая строка ввода содержит строку $$$s$$$ длины $$$n$$$, состоящую из символов '(' и ')' — начальная строка.

Каждая из следующих $$$q$$$ строк содержит одно целое число $$$i$$$ ($$$1\le i \le n$$$) — индекс символа, который нужно изменить в данном запросе.

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

Для каждого запроса выведите «YES», если строка проходима после этого запроса, и «NO» в противном случае.

Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «YEs», «Yes», «Yes» и «YES» будут распознаны как положительные ответы.

Примеры
Входные данные
10 9
(())()()))
9
7
2
6
3
6
7
4
8
Выходные данные
YES
YES
NO
NO
YES
NO
YES
NO
NO
Входные данные
3 2
(()
2
3
Выходные данные
NO
NO
Примечание

В первом примере:

  • После первого запроса строка имеет вид (())()()(). Эта строка является правильной скобочной последовательностью, поэтому ее можно пройти, просто перемещаясь вправо.
  • После второго запроса строка имеет вид (())()))(). Если вы сдвинетесь один раз вправо, затем влево, затем пройдете вправо до конца строки, вы получите строку (((()(())())(), которая является правильной скобочной последовательностью.
  • После третьего запроса строка имеет вид ()))())())(). Мы можем показать, что эта строка не является проходимой.
Во втором примере, строки после запросов равны ()) и ()(, ни одна из которых не является проходимой.