Tony the monkey is playing in the forest when he stumbles upon a bizarre grid with ~N~ rows and ~M~ columns. The grid contains cells, each consisting of either puddles or land. Intrigued by his discovery, Tony decides to cross it. He can start on any cell consisting of land in row ~1~ and wants to reach row ~N~. However, Tony is deathly afraid of water and needs a way to cross the puddles!

Instead of jumping over the puddles or wearing boots, Tony decides to build a canoe! Before entering the grid, Tony can build a single canoe of length ~L~ and width ~1~ — he can use this canoe to cross any subgrid of puddles that can fit the entire length of the canoe. If Tony is on a land cell, he can lay down his canoe in the direction of an adjacent puddle cell, as long as the puddle can accommodate the length of the canoe. Once in the water, he can move either forward or backward in the direction he placed the canoe but cannot turn (Tony doesn't know how to steer). Once the tip of his canoe eventually hits land, Tony can get off his canoe on the cell of land he hits.

For example, if Tony is in cell ~(r, c)~ and an adjacent puddle cell is cell ~(r, c-1)~, he is able to set his canoe on cell ~(r, c-1)~ pointing towards decreasing ~c~ and freely move the canoe parallel to the ~r~ axis, as long as the canoe is not occupying a land cell.

While on land, Tony can move to any adjacent land cell. Since Tony can carry the canoe above his head and over any nearby water or vegetation, the size of his canoe is not limited by his surroundings while on land.

By using some sequence of walking and canoeing, Tony wants to eventually reach row ~N~. For each cell in row ~N~, you are to tell Tony the largest possible ~L~ such that he is able to reach that cell. If ~L~ can be arbitrarily large, tell him 0. If the cell is a puddle or unreachable, tell him -1.

Constraints

~2 \le N, M \le 2 \times 10^3~

Subtask 1 [5%]

~2 \le N, M \le 400~

Subtask 2 [95%]

No additional constraints.

Input Specification

The first line contains two space-separated integers ~N~ and ~M~.

The next ~N~ lines each contain ~M~ characters representing the grid, with # representing land and . representing a puddle.

Output Specification

Output ~M~ integers, each representing the largest ~L~ possible for each cell in row ~N~. If ~L~ can be infinitely large, output 0. If cell ~j~ of row ~N~ is a puddle or is unreachable, output -1.

Sample Input 1

4 5
#####
.....
##.##
#.#.#

Sample Output 1

1 -1 2 -1 1

Explanation for Sample 1

The following diagrams show a possible path that Tony can take to get from some cell on row ~1~ to each of the land cells on row ~N~. Light blue cells represent puddle cells and brown cells represent land cells. A red arrow means a move with a canoe that has the same length as the arrow and a white arrow means a move on land.

In the following description, cell ~(1, 1)~ is the top-leftmost cell and cell ~(N, M)~ is the bottom-rightmost cell.

In the rightmost diagram, Tony wants to go to the rightmost cell on row ~N~ — cell ~(4, 5)~. He starts at cell ~(1, 3)~ and places a canoe of length ~1~ in the direction of the topmost red arrow which spans cell ~(2, 3)~. He then paddles forward to cell ~(3, 3)~ allowing him to exit the canoe at cell ~(4, 3)~.

Tony then places a canoe of length ~1~ in the direction of the bottommost red arrow which spans cell ~(4, 4)~, allowing him to exit the canoe at cell ~(4, 5)~ and reach his destination. The answer for this destination cell is therefore ~1~, and this can be proven to be the maximum ~L~ that reaches this destination.

Sample Input 2

2 4
###.
...#

Sample Output 2

-1 -1 -1 -1

Explanation for Sample 2

Note that placing a canoe in the position and orientation of the red arrow is not allowed. Canoes can only be placed from a cell in row ~1~ in the direction of the blue arrows.

Sample Input 3

2 2
##
##

Sample Output 3

0 0