Вам дан ряд из \(n\) клеток, изначально каждая клетка белого цвета. С помощью печати, вы можете покрасить любые две соседние клетки так, что одна из них становится красной, а другая синей. Печать можно поворачивать, то есть вы можете покрасить клетки обоими способами: как \(\color{blue}{\texttt{B}}\color{red}{\texttt{R}}\), так и \(\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\).
Во время каждого применения печати она должна находиться над заданными \(n\) клетками (то есть она не может частично находится вне этих клеток). На одну и ту же клетку печать может быть применена многократно. Каждое следующее применение печати перекрашивает обе клетки, которые под печатью.
Например, один из способов сделать рисунок \(\color{blue}{\texttt{B}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\color{blue}{\texttt{B}}\texttt{W}\) выглядит так: \(\texttt{WWWWW} \to \texttt{WW}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\texttt{W} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\texttt{W} \to \color{blue}{\texttt{B}}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}\texttt{W}\). Здесь \(\texttt{W}\), \(\color{red}{\texttt{R}}\), и \(\color{blue}{\texttt{B}}\) обозначают белую, красную, и синюю клетки, соответственно, а клетки, к которым приложили печать подчёркнуты.
Дан конечный рисунок. Возможно ли сделать его, использовав печать ноль или больше раз?
Выходные данные
Выведите \(t\) строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите «YES», если возможно получить рисунок, используя печать, и «NO» иначе.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
Примечание
Первый пример разобран в условии.
Во втором, третьем и четвёртом примерах невозможно покрасить одну клетку, так что ответ «NO».
В пятом примере можно поркасить следующим образом: \(\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{blue}{\texttt{B}}\).
В шестом примере можно поркасить следующим образом: \(\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}\).
В седьмом примере печать не нужно использовать вовсе.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
12
5
BRBBW
1
B
2
WB
2
RW
3
BRB
3
RBB
7
WWWWWWW
9
RBWBWRRBW
10
BRBRBRBRRB
12
BBBRWWRRRWBR
10
BRBRBRBRBW
5
RBWBW
|
YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO
|