У вас есть бинарная строка\(^{\text{∗}}\) \(s\) длины \(n\), и Айрис дал вам другую бинарную строку \(r\) длины \(n-1\).
Айрис собирается сыграть с вами в игру. В ходе игры вы выполните \(n-1\) операций над \(s\). В \(i\)-й операции (\(1 \le i \le n-1\)):
- Сначала вы выбираете индекс \(k\) такой, что \(1\le k\le |s| - 1\) и \(s_{k} \neq s_{k+1}\). Если выбрать такой индекс невозможно, вы проигрываете;
- Затем вы заменяете \(s_ks_{k+1}\) на \(r_i\). Обратите внимание, что это уменьшает длину \(s\) на \(1\).
Если все \(n-1\) операций выполнены успешно, вы выигрываете.
Определите, возможно ли вам выиграть в этой игре.
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если вы можете выиграть, и «NO» (без кавычек) в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Примечание
В первом наборе входных данных вы не можете выполнить первую операцию. Таким образом, вы проигрываете.
Во втором наборе входных данных вы можете выбрать \(k=1\) в единственной операции, и после этого \(s\) станет равным \(\mathtt{1}\). Таким образом, вы выигрываете.
В третьем наборе входных данных вы можете выполнить следующие операции: \(\mathtt{1}\underline{\mathtt{10}}\mathtt{1}\xrightarrow{r_1=\mathtt{0}} \mathtt{1}\underline{\mathtt{01}} \xrightarrow{r_2=\mathtt{0}} \underline{\mathtt{10}} \xrightarrow{r_3=\mathtt{1}} \mathtt{1}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2
11
0
2
01
1
4
1101
001
6
111110
10000
6
010010
11010
8
10010010
0010010
|
NO
YES
YES
NO
YES
NO
|