Type: Default 1000ms 256MiB

关灯

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

有一个 n×nn \times n 的方阵,每个位置上都有一盏灯,这些灯有亮有暗。每次,可以选择一个格子,选定后它与它相邻的格子的亮暗状态都会发生改变,在此处,相邻指的是 4-相邻 (有公共边),如下图:

image

易知,如果某一个格子被选择了偶 (奇) 数次,效果等价于它没有被选择 (被选择),因此,我们限制每个格子至多被选择 11

给定初始方阵中每盏灯的亮暗情况,请输出一个使所有灯都熄灭的方案,格式见输出格式。

如果有多个方案,输出任意一个方案,如果无解,输出 No solution

Format

Input

第一行包含一个正整数 nn,表示方阵的行数和列数。

接下来的 nn 行,每行包含一个长度为 nn 的字符串,其中第 ii 行的第 jj 个字符为 #,如果原来灯阵中第 ii 行第 jj 列的灯是亮的,否则为 .

Output

如果有解,则输出 nn 行,每行一个长度为 nn 的字符串,其中第 ii 行的第 jj 个字符为 #,如果需要选择灯阵中第 ii 行第 jj 列的格子,否则为 .

如果无解,输出一行,为 No solution

Samples

4
####
#..#
#..#
####
#..#
....
....
#..#
5
#....
.....
.....
.....
.....
No solution
5
.###.
.##.#
#...#
##..#
#####
...#.
.#..#
#....
.....
.#..#

Limitation

对于所有数据,满足 2n10002 \leq n \leq 1000

Subtask # 分值 nn 其它性质
1 88 5\leq 5
2 1313 20\leq 20
3 99 24\leq 24 保证初始所有的灯都是亮的
4 2222 100\leq 100
5 1818 300\leq 300 保证有且仅有一解 (旋转、翻转被认为是不同的解)
6 3030 1000\leq 1000

暑期模拟赛 一

Not Attended
Status
Done
Rule
IOI
Problem
5
Start at
2024-7-11 8:30
End at
2024-7-11 12:00
Duration
3.5 hour(s)
Host
Partic.
9