You are given an $n$-by-$n$ grid where each square is colored either black or white. A grid is correct if all of the following conditions are satisfied:
 - Every row has the same number of black squares as it has white squares.
 - Every column has the same number of black squares as it has white squares.
 - No row or column has $3$ or more consecutive squares of the same color.

Given a grid, determine whether it is correct.

-----Input-----
The first line contains an integer $n$ ($2\le n\le 24$; $n$ is even). Each of the next $n$ lines contains a string of length $n$ consisting solely of the characters ‘B’ and ‘W’, representing the colors of the grid squares.

-----Output-----
If the grid is correct, print the number $1$ on a single line. Otherwise, print the number $0$ on a single line.

-----Examples-----
Sample Input 1:
4
WBBW
WBWB
BWWB
BWBW
Sample Output 1:
1

Sample Input 2:
4
BWWB
BWBB
WBBW
WBWW
Sample Output 2:
0

Sample Input 3:
6
BWBWWB
WBWBWB
WBBWBW
BBWBWW
BWWBBW
WWBWBB
Sample Output 3:
0

Source: kattis | Difficulty: EASY


Solutions: