Little Pete Dirichlet likes pigeons a lot. He comes to the dovecote everyday, puts pigeons into holes and counts how many pigeons there are in each hole.
One day he found n holes, and the dovecote had exactly n pigeons. Also, n was even. Pete put pigeons into holes so that each hole contains exactly one pigeon. “So beautiful!” — he had thought at first, but then looked carefully and saw this:
His inner perfectionist got upset, and he decided to change the orientation of some pigeons, so that they would sit in a
nice pattern. Pete considers these two patterns nice:
- the left half of pigeons looks in one direction, and the right half — in another direction;
- pigeons alternate: all pigeons on even spots look in one direction, and all pigeons on odd spots — in another direction.
Find out the smallest amount of pigeons whose orientation needs to be changed to form a nice pattern.
Input
The first line contains one even integer n — the amount of pigeons (2 ≤ n ≤ 100).
Then, three lines of length 5n − 1 each follow. They describe n pigeons. Every pigeon takes up four characters in each of the three lines. Pigeons, oriented to the left and to the right respectively, are denoted like this:
<@.. ..@>
.OO= =OO.
./\. ./\.
Characters used are “.
” (code 46), “/
” (code 47), “<
” (code 60), “=
” (code 61), “>
” (code 62), “@
” (code 64), “O
” (code 79), “\
” (code 92). Each pair of adjacent pigeons are separated with a column of periods. It is guaranteed that lines contain nothing except for descriptions of pigeons and columns separating them.
Output
Output one number — the answer to the problem.
Samples
input | output |
---|
8
..@>.<@...<@.....@>...@>...@>.<@...<@..
=OO...OO=..OO=.=OO..=OO..=OO...OO=..OO=
./\.../\.../\.../\.../\.../\.../\.../\.
| 4
|
4
..@>...@>.<@.....@>
=OO..=OO...OO=.=OO.
./\.../\.../\.../\.
| 1
|
Notes
In the first example he needs to rotate the first, the fourth and the last two pigeons, then the first half would look to the left, and right half — to the right.
In the second example he needs to rotate the first pigeon so they would alternate.
Problem Author: Kirill Borozdin
Problem Source: Ural School Programming Contest 2019