ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Regional School Programming Contest 2019

About     Problems     Submit solution     Judge status     Standings
Contest is over

L. Pigeonhole Principle

Time limit: 0.5 second
Memory limit: 256 MB
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:
Problem illustration
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

inputoutput
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
To submit the solution for this problem go to the Problem set: 2149. Pigeonhole Principle