Дана бинарная строка \(a\) длины \(n\). За одну операцию можно выбрать любой префикс \(a\) с равным числом символов \(0\) и \(1\). Затем все символы в префиксе меняются: каждый \(0\) становится \(1\), а каждый \(1\) — \(0\).
Например, предположим, что \(a=0111010000\).
- В первой операции можно выбрать префикс длины \(8\), так как он имеет четыре \(0\) и четыре \(1\): \([01110100]00\to [10001011]00\).
- Во второй операции можно выбрать префикс длины \(2\), так как он имеет один \(0\) и одну \(1\): \([10]00101100\to [01]00101100\).
- Для третьей операции запрещено выбирать префикс длины \(4\), так как он имеет три \(0\) и одну \(1\).
Можете ли вы преобразовать строку \(a\) в строку \(b\), сделав некоторое конечное количество операций (возможно, ни одной)?
Выходные данные
Для каждого набора входных данных выведите «YES», если возможно преобразовать \(a\) в \(b\), или «NO», если это невозможно. Вы можете выводить каждый символ в любом регистре.
Примечание
Первый набор входных данных разобран в условии.
Во втором наборе входных данных мы преобразуем \(a\) в \(b\), используя ноль операций.
В третьем наборе входных данных нельзя сделать ни одну операцию, поэтому преобразовать \(a\) в \(b\) невозможно.
В четвертом наборе входных данных, вот одно из таких преобразований:
- Выберите префикс длины \(2\), чтобы получить \(100101010101\).
- Выберите префикс длины \(12\), чтобы получить \(011010101010\).
- Выберите префикс длины \(8\), чтобы получить \(100101011010\).
- Выберите префикс длины \(4\), чтобы получить \(011001011010\).
- Выберите префикс длины \(6\), чтобы получить \(100110011010\).
В пятом наборе входных данных единственной разрешенной операцией является преобразование \(a\) в \(111000\). Но для получившейся строки единственная разрешенная операция — это вернуться к строке, с которой мы начали, поэтому мы не можем преобразовать \(a\) в \(b\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
10
0111010000
0100101100
4
0000
0000
3
001
000
12
010101010101
100110011010
6
000111
110100
|
YES
YES
NO
YES
NO
|