403020: GYM100971 A Treasure Island

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Treasure Islandtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Pirate John Silver has found a map depicting exactly one island in a sea. The map is a piece of cloth divided into cells: n cells in height and m cells in width. John Silver knows that every cell denotes either land or water, but some of the cells are erased, and now it's absolutely impossible to say what these cells represent.

Help John Silver to restore the map of the island. An island is a non-empty set of land cells connected in four directions (up, down, left and right).

Input

The first line contains two integers n and m (1 ≤ n,  m ≤ 50) — the sizes of the map.

Each of the next n lines contains m characters and describes the map. A character is equal to «#» if this cell is a water cell, «.» if it's a land cell, and «?» if this cell is erased.

It's guaranteed that the input contains at least one character «.» and at least one character «?».

Output

If it's not possible to restore the map so that it would depict exactly one island, output «Impossible».

If the map can be restored in a unique way, output n lines of m characters in the same format as they are in the input, but replacing «?» with «.» or «#».

And if there are several correct ways to restore the map, output «Ambiguous».

ExamplesInput
5 7

#######

#..#..#

#..?..#

#..#..#

#######
Output
#######

#..#..#

#.....#

#..#..#

#######
Input
5 7

#######

#...#.#

#.?.?.#

#.#...#

#######
Output
Ambiguous
Input
5 7

#######

#.#.#.#

#.#?#.#

#.#.#.#

#######
Output
Impossible

加入题单

上一题 下一题 算法标签: