Problem Description

You are given a square block of size $ N $ × $ N $. The blocks are provided in three types: o blocks, x blocks, and . blocks.

You know that after a while, all . blocks will disappear, and the blocks above them will fall down.

Before they disappear, you can convert each . block into one of the following two types of blocks:

• + block: A normal block that does not disappear
• - block: A block that does not disappear and does not fall down

Your goal is to maximize the sum of the maximum number of connected o blocks and the maximum number of connected x blocks in the up, down, left, and right directions after the . blocks have disappeared.

Given the initial state of the blocks, output the state of the blocks after the conversion.

Input Format

$ S_1 $ $ S_2 $ : $ S_N $

Output Format

Output the modified block configuration in the same format as the input. Use + for + blocks and - for - blocks.

The sum of the connected numbers will be the score for that case, and the sum of the scores for 10 inputs will be your submission score.

Sample Input and Output

Sample Input #1

o.xx..ox..
..o.xx.o.x
.xxoo...o.
o..x.ox.x.
..o.o..ox.
..x..oo..x
.o.x.xxo..
x..xo.xxoo
.o..oox...
x.o.x.ox.x

Sample Output #1

o.xx..ox..
..o.xx.o.x
-xxoo...o.
o..x.ox.x.
..o.o+.ox.
..x..oo..x
.o.x.xxo..
x.+xo-xxoo
.o..oox+++
x.o.x.ox.x

Sample Input #2

.oo...x....xoo.xooooo.xx..xxo..xx.xoox.o..x..oo.o.
o..ox.xoxxox.xo..ooxx.ox.o.xooo.....x...ooxxo.o..x
x...x..oxxox.o..oxox.xoxo...oxo..oo....oxx.x...x.x
.xoo.........xo.xxx...x.o.xoox...o.o.x..ox.xx.oxo.
o.x...x.x.o.o...xo..oxxxo.xoo.xo.xo.ox.o...o...o..
xo.o.x..o.xx..o.....x..o.o....x.....ooo.oo.ooxx..o
.xx.o.xoo.x.xxx.x.o.xxoo.ox.o.oo.x.xxo..ox.x.o.o.o
.ox.o..xxo.ooxo.x.x.xx.xx.x...ooo.o..x....xo....ox
xx..ox.xx.x.x...ooxxox.oxx.o.oo.xo.o..x.x.xx..xxx.
o....o..x..xoxxx....o....x....x.o.o.x....ooo...o..
.xo.x...xox.............xo..xo....x..xoo.xx...x.ox
.oxxxxx.xx..o.oxoxx...x...x..x.oxxoxxo..oxx..xx...
.o..x.x.o...x..oo..o.x..xxox..o.oo.....x..x..o.oo.
ox.xo.xx.x..xo.oxooo..o.xxo.xox.o.x..xoo..o.x..oo.
.xoox...xoox...ooxx......o.oox....x.x.ox..o.ox.o.x
.o..x.xx..x....o..x.ox...oxooo....x..x.......o..x.
.o.xx..x..ox...o.o.xoo..oxx..oxo.oo..o.x.o.o....oo
x..xx.....x...o.xx.x..xo..x.oxx...xo.o...xx...xo.o
xx.oox.oxxo...ox...o.x..xo.oooxo..x..ox.ox...o...x
.oo...o.....o...xooxoxox.x.x...oo..xo.x.oo.x.xxxo.
oox..o.x.xo...oox.x..x..o.x.xxxo.x.x...o.o..o.....
xo.xx.o.x.xx.xo..oox..o..xoo...xo.o..ooo......oxox
.o..xx..xxo.....x...o.x..xxoxooxo..ooo.xx.....x..o
o..o.x..x.o.ox.oxx.o.xo.xox.o....o.o.x.ox...x.xox.
...o..oxoooo.x.o..oo....xo.xxxxxox..o.o.o....oo.o.
.xxo..x.x.oxoo.x.o....xxoxoo...ooxx.ox...ooo..x.x.
.xo..xxx.o..ox.oo....oox...xxo...oxx.o.ooo.o...oox
....ox.x.oo.o.x..x....o...o...x.oxx.oxo..o...oooo.
xxx..ox...x.x.x.o.x......xx..xx.ox.x......o.x..o.x
...oox.xox.ox.xx.x....x.oxxx..xxoxo.o.o....oxx...x
xoo.....ooxxxoxxxxx.....oxxx.....x..x...x..o.x..oo
..xo.oooxo...xx..x....x..oox.x.oxooo.oxoox...oxxo.
...ox.o.xo.oxxx....o..xooxox..x.xo...oo.xooo.x.xox
xx..o.oo...ox.x.x.ooxxxox...o..ox...ox....xx..xo..
xx.ooo..o.xoox.x.oox.o.xxxoooox.o..oo..x.x.xx....o
.oo...oxo.x.o.xx.o..xoxxox..x.xx.......xoxoxx.oxoo
...ox.ooooo.xxx.x..o.x.x.....xo..oo.xx..xo....ooox
.o.xx..o..xoxxo.xoo..xooo.xx.ox.xxxo.o.xo..o...x..
.xx...xoo.x.x.o.xo.o.xoxxo..oxo.ox....xoox.ox.xxxo
x.x..xox.....oxo..oo.ooxo...xo...ox.o..oo....ox.xo
.xx....xx.o....x.xoo.x.x.oxxooxxo..x..x..xxxxxo.ox
.o.x.x..x.oxoxx.xo..ox...ox.o......x.xxo...oo.oxx.
xx.xoxo.oo....ooxoxxxxxxxxoxxxx...oxx.o..oo.xo..xo
xx....o.o.xo.oox...o..o.x..o..x..x..xoxooxo.ox.oox
o.x..o.x..o.oo..ooo.x.......x.xx.o...oo..ox.x.xxx.
.xxoxoxxoo.o.o......xx..xxo.x....oox.x.xo.x..x....
oxx.oox....oxxx....x.oox..o.xx..xoxx.x.oo.o.o.x..x
....x.x.ox.xooxo.x..x.xo....oxoo..o.x.oo..o..x..x.
..o.o.xx....o...oooo...x.oox..oxox.x.x.x.xx...o.oo
..x.o.xo...xxx.x.ox.....oxo..ooxo..x.o.x..ooooxxox

Sample Output #2

.oo...x....xoo.xooooo.xx..xxo..xx.xoox.o..x..oo.o.
o..ox.xoxxox.xo..ooxx.ox.o.xooo.....x...ooxxo.o..x
x...x..oxxox.o..oxox.xoxo...oxo..oo....oxx.x...x.x
.xoo.........xo.xxx...x.o.xoox...o.o.x..ox.xx.oxo.
o.x...x.x.o.o...xo..oxxxo.xoo.xo.xo.ox.o...o...o..
xo.o.x..o.xx..o.....x..o.o....x.....ooo.oo.ooxx..o
.xx.o.xoo.x.xxx.x.o.xxoo.ox.o.oo.x.xxo..ox.x.o.o.o
.ox.o..xxo.ooxo.x.x.xx.xx.x...ooo.o..x....xo....ox
xx..ox.xx.x.x...ooxxox.oxx.o.oo.xo.o..x.x.xx..xxx.
o....o..x..xoxxx....o....x....x.o.o.x....ooo...o..
.xo.x...xox.............xo..xo....x..xoo.xx...x.ox
.oxxxxx.xx..o.oxoxx...x...x..x.oxxoxxo..oxx..xx...
.o..x.x.o...x..oo..o.x..xxox..o.oo.....x..x..o.oo.
ox.xo.xx.x..xo.oxooo..o.xxo.xox.o.x..xoo..o.x..oo.
.xoox...xoox...ooxx......o.oox....x.x.ox..o.ox.o.x
.o..x.xx..x....o..x.ox...oxooo....x..x.......o..x.
.o.xx..x..ox...o.o.xoo..oxx..oxo.oo..o.x.o.o....oo
x..xx.....x...o.xx.x..xo..x.oxx...xo.o...xx...xo.o
xx.oox.oxxo...ox...o.x..xo.oooxo..x..ox.ox...o...x
.oo...o.....o...xooxoxox.x.x...oo..xo.x.oo.x.xxxo.
oox..o.x.xo...oox.x..x..o.x.xxxo.x.x...o.o..o.....
xo.xx.o.x.xx.xo..oox..o..xoo...xo.o..ooo......oxox
.o..xx..xxo.....x...o.x..xxoxooxo..ooo.xx.....x..o
o..o.x..x.o.ox.oxx.o.xo.xox.o....o.o.x.ox...x.xox.
...o..oxoooo.x.o..oo....xo.xxxxxox..o.o.o....oo.o.
.xxo..x.x.oxoo.x.o....xxoxoo...ooxx.ox...ooo..x.x.
.xo..xxx.o..ox.oo....oox...xxo...oxx.o.ooo.o...oox
....ox.x.oo.o.x..x....o...o...x.oxx.oxo..o...oooo.
xxx..ox...x.x.x.o.x......xx..xx.ox.x......o.x..o.x
...oox.xox.ox.xx.x....x.oxxx..xxoxo.o.o....oxx...x
xoo.....ooxxxoxxxxx.....oxxx.....x..x...x..o.x..oo
..xo.oooxo...xx..x....x..oox.x.oxooo.oxoox...oxxo.
...ox.o.xo.oxxx....o..xooxox..x.xo...oo.xooo.x.xox
xx..o.oo...ox.x.x.ooxxxox...o..ox...ox....xx..xo..
xx.ooo..o.xoox.x.oox.o.xxxoooox.o..oo..x.x.xx....o
.oo...oxo.x.o.xx.o..xoxxox..x.xx.......xoxoxx.oxoo
...ox.ooooo.xxx.x..o.x.x.....xo..oo.xx..xo....ooox
.o.xx..o..xoxxo.xoo..xooo.xx.ox.xxxo.o.xo..o...x..
.xx...xoo.x.x.o.xo.o.xoxxo..oxo.ox....xoox.ox.xxxo
x.x..xox.....oxo..oo.ooxo...xo...ox.o..oo....ox.xo
.xx....xx.o....x.xoo.x.x.oxxooxxo..x..x..xxxxxo.ox
.o.x.x..x.oxoxx.xo..ox...ox.o......x.xxo...oo.oxx.
xx.xoxo.oo....ooxoxxxxxxxxoxxxx...oxx.o..oo.xo..xo
xx....o.o.xo.oox...o..o.x..o..x..x..xoxooxo.ox.oox
o.x..o.x..o.oo..ooo.x.......x.xx.o...oo..ox.x.xxx.
.xxoxoxxoo.o.o......xx..xxo.x....oox.x.xo.x..x....
oxx.oox....oxxx....x.oox..o.xx..xoxx.x.oo.o.o.x..x
....x.x.ox.xooxo.x..x.xo....oxoo..o.x.oo..o..x..x.
..o.o.xx....o...oooo...x.oox..oxox.x.x.x.xx...o.oo
..x.o.xo...xxx.x.ox.....oxo..ooxo..x.o.x..ooooxxox

Notes/Hints

Constraints

• $ N $ = $ 50 $
• $ S_i $ is a string of $ N $ characters, and the $ j $th character $ S_{i,j} $ is one of o, x, or ..
• The input is generated randomly such that each character has a $50\%$ chance of being ., and a $25\%$ chance of being either o or x.

Sample Explanation 1

This input uses a smaller, non-existent input for explanation purposes. When all . blocks disappear, the state will be as follows. The diagram represents o blocks as ○, x blocks as ×, + blocks as ★, and - blocks as ■.

见题面 Input 部分

见题面 Output 部分