У Циншань есть строка \(s\), а у Даниэля — строка \(t\). Обе строки содержат только символы \(\texttt{0}\) и \(\texttt{1}\).
Строка \(a\) длины \(k\) является хорошей тогда и только тогда, когда
- \(a_i \ne a_{i+1}\) для всех \(i=1,2,\ldots,k-1\).
Например, строки \(\texttt{1}\), \(\texttt{101}\), \(\texttt{0101}\) — хорошие, а \(\texttt{11}\), \(\texttt{1001}\), \(\texttt{001100}\) — плохие.
Циншань хочет сделать \(s\) хорошей. Для этого она может выполнить следующую операцию любое количество раз (возможно, нулевое):
- вставить \(t\) в любую позицию \(s\) (получив новую строку \(s\)).
Пожалуйста, скажите Циншань, можно ли сделать \(s\) хорошей.
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если можно сделать \(s\) хорошей, и «NO» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом наборе входных данных строка \(s\) изначально хорошая, поэтому можно получить хорошую \(s\), выполнив ноль операций.
Во втором наборе входных данных можно выполнить следующие две операции (вставленная строка \(t\) подчеркнута):
- \(\texttt{1}\underline{\texttt{010}}\texttt{11}\)
- \(\texttt{10101}\underline{\texttt{010}}\texttt{1}\)
и получить \(s = \texttt{101010101}\), что является хорошей строкой.
В третьем наборе входных данных нет способа сделать \(s\) хорошей после любого количества операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1
1
0
3 3
111
010
3 2
111
00
6 7
101100
1010101
10 2
1001001000
10
|
Yes
Yes
No
No
No
|