Problem Description

E869120 is considering going to a skate rink consisting of a grid of $H$ rows and $W$ columns. The top-left cell is $(1, 1)$ and the bottom-right cell is $(H, W)$.
The skate rink consists of one goal cell, some ice cells, and some concrete cells. He plans to start from a specific location and reach the goal in the shortest time possible.

The skate rink has the following properties:

• Ice cells are slippery, so you continue moving in the same direction until you reach a concrete cell or the goal cell. However, going out of the skate rink results in a game over.
• You can only change the direction of movement when you are stationary.
• Reaching the goal cell results in a game clear.

However, his skateboard is on the verge of breaking. Therefore, the speed changes as follows:

• It takes him $k$ seconds to move one cell. Initially, $k=1$.
• When he stops on a concrete cell, $k$ increases by 1.
• He can only move in four directions: up, down, left, and right.

Before going to the skate rink, he wants to know for every cell $(i, j)$, how many seconds it takes to reach the goal starting from cell $(i, j)$.
Write a program to help him.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ c_{1,1} $$ c_{1,2} $$ c_{1,3} $ ... $ c_{1,W} $ $ c_{2,1} $$ c_{2,2} $$ c_{2,3} $ ... $ c_{2,W} $ $ c_{3,1} $$ c_{3,2} $$ c_{3,3} $ ... $ c_{3,W} $ ... $ c_{H,1} $$ c_{H,2} $$ c_{H,3} $ ... $ c_{H,W} $

The first line contains the size of the skate rink $H$, $W$.
The next $H$ lines describe the state of the skate rink, where each cell is represented by the following characters:

• . represents an ice cell.
• # represents a concrete cell.
• G represents the goal cell.

Output Format

Output in the following format:

$ d_{1,1} $ $ d_{1,2} $ $ d_{1,3} $ ... $ d_{1,W} $ $ d_{2,1} $ $ d_{2,2} $ $ d_{2,3} $ ... $ d_{2,W} $ $ d_{3,1} $ $ d_{3,2} $ $ d_{3,3} $ ... $ d_{3,W} $ ... $ d_{H,1} $ $ d_{H,2} $ $ d_{H,3} $ ... $ d_{H,W} $

$ d_{i,j} $ represents the shortest time to reach the goal starting from cell $(i, j)$.
If it is impossible to reach the goal by any means, $ d_{i,j} $ should be $-1$.

Sample Input and Output

Sample Input #1

6 6
......
.#....
......
......
......
...#.G

Sample Output #1

-1 -1 -1 9 -1 5
-1 -1 -1 8 -1 4
-1 -1 -1 7 -1 3
-1 -1 -1 6 -1 2
-1 -1 -1 5 -1 1
7 6 5 2 1 0

Sample Input #2

1 8
#####G##

Sample Output #2

15 10 6 3 1 0 1 3

Sample Input #3

9 9
....#..#.
#........
....#....
.#......#
...###...
##....#.#
....#...#
#....#...
.#.#..#.G

Sample Output #3

54 37 52 29 38 38 17 53 18
43 36 60 28 37 37 16 65 17
40 35 38 27 26 36 15 39 16
35 22 21 20 19 18 14 16 10
28 27 26 16 16 25 13 36 9
28 17 16 15 14 13 7 9 5
18 17 16 14 8 7 6 5 2
41 22 52 13 15 37 5 51 1
22 14 13 7 6 5 2 1 0

Notes/Hints

Constraints

• $ H $ is an integer between $ 1 $ and $ 777 $ inclusive.
• $ W $ is an integer between $ 1 $ and $ 777 $ inclusive.
• There are between $ 0 $ and $ 7,777 $ concrete cells in the skate rink.
• There is exactly one goal cell in the skate rink.

Subtasks

Subtask $ 1 $ \[$ 40 $ points\]

• $ H = 1 $.
• $W \leq 17$.

Subtask $ 2 $ \[$ 160 $ points\]

• $H \leq 17$.
• $W \leq 17$.
• There are at most $ 77 $ concrete cells in the skate rink.

Subtask $ 3 $ \[$ 190 $ points\]

• $H \leq 177$.
• $W \leq 177$.
• There are at most $ 377 $ concrete cells in the skate rink.

Subtask $ 3 $ \[$ 410 $ points\]

• No additional constraints.

Sample Explanation 1

The state of the skate rink is as shown in the figure. Starting from cell $(2, 4)$, it takes $ 8 $ seconds as shown in the figure.

Sample Explanation 2

The state of the skate rink is as shown in the figure. Starting from cell $(1, 1)$, it takes $ 15 $ seconds as shown in the figure.

见题面 Input 部分

见题面 Output 部分