Три-бітний комп'ютер#4379
Вчені в Королівстві Байтленду прагнуть розробити новий тип комп'ютера, а саме Три-бітний комп'ютер (TBC). Вони прогнозують, що нова машина матиме змогу розв'язати багато складних і досі нерозв'язаних задач. Однак, спочатку необхідно вирішити певні технічні труднощі. Вас попросили допомогти вченим у вирішенні однієї з них.
Зараз вчені працюють над процедурою ініціалізації пам'яті комп'ютера. Поточна версія TBC має бітів пам'яті, пронумерованих від до . Кожен біт може мати одне з трьох значень , , або бути неініціалізованим. Комп'ютер підтримує наступні операції ініціалізації пам'яті:
- Два послідовних неініціалізованих біти, тобто біти з номерами та i+1 при 1 \leq i < n, можна встановити у два різних значення. - Два послідовних біти, один з яких неініціалізований, а інший вже має значення , можна встановити у два різних значення, жодне з яких не дорівнює .
Наприклад, наступна процедура ініціалізації є можливою для n = 4: uuuu \rightarrow uuab \rightarrow ucbb \rightarrow babb, де позначає неініціалізований біт пам'яті.
Завдання:
Напишіть програму, яка: - зчитує значення, до яких потрібно ініціалізувати пам'ять, - перевіряє, чи можлива така ініціалізація, - записує відповідь у вихідний файл.
Перший рядок вхідного файлу містить одне додатне число (1 \leq n \leq 10) — кількість шаблонів. Далі йде опис шаблонів. Опис кожного шаблону складається з двох послідовних рядків. Перший рядок містить додатне число l_i (1 \leq l_i \leq 100\,000) — довжину -го шаблону (тобто розмір пам'яті комп'ютера). Другий рядок містить послідовність з l_i літер , , — сам шаблон.
Вихідний файл повинен містити рядків, по одному для кожного шаблону. У -му рядку повинно міститися одне слово YES, якщо ініціалізація можлива, або NO — інакше.
Приклад 1