Школьники Алиса и Ибрагим — лучшие друзья. У Ибрагима скоро день рождения, и по этому поводу Алиса решила подарить ему новый пазл. Пазл можно представить в виде матрицы из $$$2$$$ строк и $$$n$$$ столбцов, каждый элемент которой $$$0$$$ или $$$1$$$. За один ход можно поменять местами два элемента, стоящие в соседних клетках.
Более формально, будем считать, что строки матриц пронумерованы сверху вниз от $$$1$$$ до $$$2$$$, а столбцы — слева направо от $$$1$$$ до $$$n$$$. Обозначим клетку на пересечении строки $$$x$$$ и столбца $$$y$$$ за $$$(x, y)$$$. Будем считать две клетки $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ соседними, если $$$|x_1 - x_2| + |y_1 - y_2| = 1$$$.
Алисе не нравится, какой рисунок образуют клетки пазла в данный момент. Она придумала свой рисунок, с которым и планирует подарить Ибрагиму новый пазл, но для этого нужно привести пазл в соответствующее состояние.
В конце учебного года у Алисы очень плотное расписание, и она не хочет тратить на эту задачу много времени. Помогите Алисе найти минимальное количество ходов, за которое она может получить свой рисунок, или скажите, что это невозможно.
В первой строке вводится одно целое число $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — количество столбцов в пазле.
Следующие две строки описывают рисунок, образованный пазлом в данный момент. В каждой строке вводятся $$$n$$$ целых чисел, каждое из которых равно $$$0$$$ или $$$1$$$.
Следующие две строки описывают желаемый рисунок Алисы в том же формате.
Если Алиса не ошиблась и её рисунок можно получить, найдите и выведите минимальное необходимое количество ходов, иначе выведите $$$-1$$$.
Тесты к этой задаче состоят из 8 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | ||||
| Группа | Баллы | $$$n$$$ | Необходимые группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 16 | $$$n \le 7$$$ | 0 | |
| 2 | 11 | $$$n \le 17$$$ | 0, 1 | |
| 3 | 14 | $$$n \le 50$$$ | 0 – 2 | |
| 4 | 8 | $$$n \le 300$$$ | 0 – 3 | |
| 5 | 16 | $$$n \le 3000$$$ | 0 – 4 | |
| 6 | 16 | – | – | Вторая строка каждого пазла состоит из нулей. |
| 7 | 9 | – | 6 | Вторая строка второго пазла состоит из нулей. |
| 8 | 10 | – | 0 – 7 |
5 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0
5
3 1 0 0 0 0 0 0 0 0 0 0 0
-1
В первом примере из условия подойдет следующая последовательность обменов:
$$$(2, 1), (1, 1)$$$
$$$(1, 2), (1, 3)$$$
$$$(2, 2), (2, 3)$$$
$$$(1, 4), (1, 5)$$$
$$$(2, 5), (2, 4)$$$
Можно показать, что меньшим числом обменов обойтись нельзя, поэтому ответ равен $$$5$$$.
Во втором примере из условия никакая последовательность ходов не приводит пазл к нужному виду.
