Марк только что купил светильник из \(n\) лампочек. Состояние лампочек можно описать бинарной строкой \(s = s_1s_2\dots s_n\), где \(s_i=\texttt{1}\) означает, что \(i\)-я лампочка включена, а \(s_i=\texttt{0}\) означает, что \(i\)-я лампочка выключена.
К сожалению, лампочки сломаны, и Марк может выполнять единственную операцию, чтобы изменять состояние лампочек:
- выбрать индекс \(i\) из чисел \(2,3,\dots,n-1\) такой, что \(s_{i-1}\ne s_{i+1}\);
- переключить \(s_i\): если \(s_i\) равно \(\texttt{0}\), установить для \(s_i\) значение \(\texttt{1}\), и наоборот.
Марк хочет, чтобы состояние лампочек описывалось другой бинарной строкой \(t\). Помогите Марку определить минимальное количество операций, чтобы достичь это состояние.
Выходные данные
Для каждого набора входных данных выведите строку, содержащую минимальное количество операций, которые должен выполнить Марк, чтобы преобразовать состояние лампочек из \(s\) в \(t\). Если такой последовательности операций не существует, выведите \(-1\).
Примечание
В первом наборе входных данных примера одна из последовательностей операций, обеспечивающая минимальное количество операций, следующая:
- выбрать \(i=3\), заменив \(\texttt{01}\color{red}{\texttt{0}}\texttt{0}\) на \(\texttt{01}\color{red}{\texttt{1}}\texttt{0}\);
- выбрать \(i=2\), заменив \(\texttt{0}\color{red}{\texttt{1}}\texttt{10}\) на \(\texttt{0}\color{red}{\texttt{0}}\texttt{10}\).
Во втором наборе входных данных искомой последовательности операций не существует, потому что нельзя изменить ни первый, ни последний символ \(s\).
В третьем наборе входных данных, хотя первые символы \(s\) и \(t\) совпадают и последние символы \(s\) и \(t\) одинаковы, можно показать, что не существует последовательности операций, которая удовлетворяет условию.
В четвертом наборе входных данных одна из последовательностей, обеспечивающая минимальное количество операций, выглядит следующим образом:
- выбрать \(i=3\), заменив \(\texttt{00}\color{red}{\texttt{0}}\texttt{101}\) на \(\texttt{00}\color{red}{\texttt{1}}\texttt{101}\);
- выбрать \(i=2\), заменив \(\texttt{0}\color{red}{\texttt{0}}\texttt{1101}\) на \(\texttt{0}\color{red}{\texttt{1}}\texttt{1101}\);
- выбрать \(i=4\), заменив \(\texttt{011}\color{red}{\texttt{1}}\texttt{01}\) на \(\texttt{011}\color{red}{\texttt{0}}\texttt{01}\);
- выбрать \(i=5\), заменив \(\texttt{0110}\color{red}{\texttt{0}}\texttt{1}\) на \(\texttt{0110}\color{red}{\texttt{1}}\texttt{1}\);
- выбрать \(i=3\), заменив \(\texttt{01}\color{red}{\texttt{1}}\texttt{011}\) на \(\texttt{01}\color{red}{\texttt{0}}\texttt{011}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
0100
0010
4
1010
0100
5
01001
00011
6
000101
010011
|
2
-1
-1
5
|