Cave Trip

Interview

Time limit1sMemory limit1024 MB

Summary

Find the shortest path from the '@' cell to any border cell of a grid cave and mark it with asterisks, or print -1 if no exit is reachable.

Level: Easy3 of 10
Topics: BFS, Graph, Matrix
Solved: No attempts yet

Problem

Speleology is undoubtedly one of the most exciting and adventurous sciences imaginable. Adventures come with dangers, of course. Yet no adventure is entirely safe. Even with precautions, all sorts of unexpected things can happen underground, and sometimes researchers need to get out of a cave as quickly as possible.

So you need to write a program that finds the shortest path to some exit.

Input

The first line of the file contains the height $H$ and width $W$ of the cave map ( $1 \le H \le 100$ , $1 \le W \le 100$ ). The next $H$ lines each contain exactly $W$ characters. A '.' marks a passable cell, a '#' marks a cave wall, and an '@' marks the starting position of the research team. A cell in row 1 or $H$ , or in column 1 or $W$ , marks an exit.

At each step, the researchers can move to a passable adjacent cell in the same row or the same column.

Output

The first line of the output is the length of the shortest path out of the cave. The next $H$ lines show the map with the path marked by asterisks ('*'). If several paths have the minimum length, print any one of them. If there is no exit, print -1 and then the original map.

Examples1

Example 1

Input

8 10
######.###
#........#
#.###.####
#.#...#..#
#.###.#.##
#.#......#
#.#@#.#..#
#.########

Expected output

9
######*###
#....**..#
#.###*####
#.#..*#..#
#.###*#.##
#.#***...#
#.#@#.#..#
#.########