It is festival day, and students are rushing to line up at their favourite booths. The festival can be modelled as an $N\times N$ grid with $N$ booths at the bottom of each column. Each cell in the grid is either empty (denoted by .) or contains a student (denoted by S). Students walk directly downwards to line up at their respective booths. There is never more than one student in one cell. What would the festival look like once all the students have lined up?

Constraints

For all test cases:

• $1\le N\le 1500$

Note: You must pass all test cases in order to earn points on this problem.

Input Specification

The first line contains one integer $N$.

The next $N$ lines each contain a string of length $N$ consisting of only . or S characters.

Output Specification

Output $N$ lines with each line containing $N$ characters of either . or S, representing the festival after the students have lined up.

Sample Input

5
S..SS
.S...
..S.S
...SS
S....

Sample Output

.....
.....
....S
S..SS
SSSSS