Юный Петя Дирихле очень любит голубей. Каждый день он приходит на голубятню, рассаживает голубей по клеткам и считает, сколько голубей получилось в каждой из клеток.
В один из дней у Пети оказалось n клеток и он нашёл на голубятне n голубей. Причём, оказалось, что n — чётное. Петя рассадил их по клеткам так, что в каждой клетке сидит ровно один голубь. «Как красиво!» — подумал, было, Петя, но тут увидел вот это:
Внутренний принципиальный перфекционист взыграл в нём, и он решил поменять ориентацию голубей, чтобы они сидели красиво. Петя считает, что голуби сидят красиво в двух случаях:
- левая половина голубей смотрит в одну сторону, а правая — в другую;
- все голуби, стоящие на чётных позициях, смотрят в одну сторону, а на нечётных — в другую.
Определите минимальное количество голубей, у которых нужно поменять ориентацию, чтобы они сидели красиво.
Исходные данные
В первой строке дано одно чётное число n — количество голубей (2 ≤ n ≤ 100).
Далее идут три строки длиной 5n − 1 символов каждая. В них описываются n голубей. Каждый голубь занимает по четыре символа в каждой из трёх строк. Так обозначаются голуби, повёрнутые влево и вправо соответственно:
<@.. ..@>
.OO= =OO.
./\. ./\.
Используются символы «.
» (код 46), «/
» (код 47), «<
» (код 60), «=
» (код 61), «>
» (код 62), «@
» (код 64), «O
» (код 79), «\
» (код 92). Каждая пара соседних голубей разделена одним столбцом из точек. Гарантируется, что в строках не содержится ничего, кроме точек и описания голубей.
Результат
Выведите единственное число — ответ на задачу.
Примеры
исходные данные | результат |
---|
8
..@>.<@...<@.....@>...@>...@>.<@...<@..
=OO...OO=..OO=.=OO..=OO..=OO...OO=..OO=
./\.../\.../\.../\.../\.../\.../\.../\.
| 4
|
4
..@>...@>.<@.....@>
=OO..=OO...OO=.=OO.
./\.../\.../\.../\.
| 1
|
Замечания
В первом примере нужно повернуть первого, четвёртого и двух последних голубей, тогда первая половину голубей будет смотреть влево, а вторая — вправо.
Во втором примере нужно повернуть первого голубя, и тогда они будут чередоваться.
Автор задачи: Кирилл Бороздин
Источник задачи: Уральская командная олимпиада по программированию 2019