Rotation Game
You have a board with height two and width W. The board is divided into 1×1 cells. Each row of the board is numbered 1 and 2 from top to bottom and each column is numbered 1 to W from left to right. We denote a cell at the i-th row in the j-th column by (i, j). Initially, some checkers are placed on some cells of the board. Here we assume that each checker looks the same. So we do not distinguish each checker. You are allowed to perform the following operations on the board:
Square rotation: Choose a 2×2 square on the board. Then move checkers in the 2×2 square such that the checkers rotate their position in the square by 90 degrees in either clockwise or counterclockwise direction.
Triangular rotation: Choose a set of cells on the board that form a triangle. Here, we call a set of cells triangle if it is formed by removing exactly one cell from a 2×2 square. In the similar manner with the square rotation, rotate checkers in the chosen triangle in either clockwise or counterclockwise direction.
The objective in this problem is to transform the arrangement of the checkers into desired arrangement by performing a sequence of rotation operations. The information of the initial arrangement and the target arrangement are given as the input. For the desired arrangement, one of the following is specified for each cell (i, j): i. cell (i, j) must contain a checker, ii. cell (i, j) must not contain a checker, or iii. there is no constraint for cell (i, j). Compute the minimum required number of operations to move the checkers so the arrangement satisfies the constraints and output it.
Input
The input is formatted as follows.
W
s_11s_11…s_1W
s_21s_21…s_2W
t_11t_11…t_1W
t_21t_21…t_2W
The first line of the input contains an integer W (2 ≤ W ≤ 2000), the width of the board. The following two lines contain the information of the initial arrangement. If a cell (i, j) contains a checker in the initial arrangement, s_ij is o. Otherwise, s_ij is .. Then an empty line follows. The following two lines contain the information of the desired arrangement. Similarly, if a cell (i, j) must contain a checker at last, t_ij is o. If a cell (i, j) must not contain a checker at last, t_ij is .. If there is no condition for a cell (i, j), t_ij is *. You may assume that a solution always exists.
Output
Output the minimum required number of operations in one line.