B. Построение ABAB
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$T$$$ длины $$$n$$$, такая что $$$T_i=$$$ 'a' для всех нечетных $$$i$$$ и $$$T_i=$$$ 'b' для всех четных $$$i$$$.

Однажды Боб сгенерировал строку $$$S$$$ с помощью следующего алгоритма.

  1. Инициализируйте $$$S$$$ пустой строкой.
  2. Удалите либо первую букву, либо последнюю букву из $$$T$$$ и добавьте её в конец $$$S$$$.
  3. Если $$$T$$$ пусто, завершите алгоритм и верните строку $$$S$$$. В противном случае вернитесь ко второму шагу.

Затем Боб написал сгенерированную строку $$$S$$$ на бумажке и забыл о ней на несколько лет. Бумажка износилась, когда Боб её нашёл, и кто-то мог тайком изменить некоторые буквы. Конечно, Боб хочет знать, изменил ли кто-то строку!

Вам дана строка $$$X$$$ длины $$$n$$$, которая состоит из 'a', 'b' и '?'.

Пожалуйста, определите, существует ли строка $$$A$$$, которая удовлетворяет следующим условиям:

  • $$$|A|=n$$$;
  • $$$A_i$$$ — либо 'a', либо 'b' для всех $$$1 \le i \le n$$$;
  • $$$A_i=X_i$$$ для всех $$$1 \le i \le n$$$, таких что $$$X_i$$$ не равно '?';
  • Строка $$$A$$$ может быть сгенерирована с помощью описанного выше алгоритма.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 200\,000$$$).

Вторая строка каждого набора входных данных содержит строку $$$X$$$ длины $$$n$$$, состоящую из 'a', 'b' и '?'.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.

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

Если существует строка $$$A$$$, которая удовлетворяет всем условиям, выведите «YES» на отдельной строке.

Если не существует строки $$$A$$$, которая удовлетворяет всем условиям, выведите «NO» на отдельной строке.

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

Пример
Входные данные
4
5
ababa
5
baaba
5
?b?ab
6
aa?b?b
Выходные данные
YES
NO
YES
NO
Примечание

Для второго набора входных данных строка «baaba» не может быть сгенерирована с помощью описанного выше алгоритма.

Для третьего набора входных данных строка «abaab» может быть сгенерирована с помощью описанного выше алгоритма:

  1. Изначально $$$T$$$ равно «ababa» и $$$S$$$ пусто.
  2. Удалите первую букву из $$$T$$$. $$$T$$$ становится «baba» и $$$S$$$ становится «a».
  3. Удалите первую букву из $$$T$$$. $$$T$$$ становится «aba» и $$$S$$$ становится «ab».
  4. Удалите последнюю букву из $$$T$$$. $$$T$$$ становится «ab» и $$$S$$$ становится «aba».
  5. Удалите первую букву из $$$T$$$. $$$T$$$ становится «b» и $$$S$$$ становится «abaa».
  6. Удалите последнюю букву из $$$T$$$. $$$T$$$ становится пустым и $$$S$$$ становится «abaab».