E - Encoding Matrices

Time limit: 1 s
Memory limit: 1024 MiB
Languages: C, C++, Java, Python, ... (details)

´╗┐Farmer John (FJ) is teaching binary numbers to his cows and they learned quickly that binary numbers have only digits 0 and 1. FJ was very happy with the obtained results, and then he decided to teach them how to create square binary matrices. However, the cows got bored after the second class. FJ was a bit sad and he thought, what if I teach my cows to encode binary matrices with other symbols?

FJ knows that his cows are not very clever. That's why he defined two simple rules for encoding binary matrices:

  1. The most frequent bit will be encoded with the symbol '*' and the least frequent bit will be encoded with the symbol 'o'
  2. In case of tie, the bit located at the top-left corner of the matrix will be encoded with the symbol '*' and the complementary bit will be encoded with the symbol 'o'.

Apparently, the cows understood these rules. However, FJ is not sure and wants to evaluate cows' skills. Write a program to encode a square binary matrix using the rules proposed by FJ.


The first line of the input contains an integer $n$ ($1 \leq n \leq 100$) representing the dimension of the matrix. The following $n$ lines contains $n$ binary symbols '0' or '1' without spaces.


The output contains the matrix obtained with the encoding mechanism proposed by FJ.

Sample test(s)

6 111000 001010 110010 001101 001110 111111
***ooo oo*o*o **oo*o oo**o* oo***o ******
2 00 11
** oo