Fire Evacuation

A fire alarm has been triggered and everyone must evacuate immediately!

The room is modeled as a \(N \times M\) rectangular grid. Each cell can be in one of three states:

• An open space (denoted by .) where people can stand and walk. Initially, every open cell has one person.
• A wall (denoted by X) which cannot be entered.
• A door (denoted by D). People can exit the room through a door.

It is guaranteed that doors are located on the boundary of the grid, and the boundary will not contain any open space (.).

Once the evacuation starts, there is no limit on how many people can occupy an open cell simultaneously. Each second, every person may either stay still or move one cell in one of the four cardinal directions (up, down, left, or right). However, because the doors are narrow, only one person per door per second can move into the door cell. As soon as a person steps into a door cell, they are considered to have safely evacuated.

Your task is to determine the minimum number of seconds needed so that everyone can evacuate safely, or report that it is impossible.

Note: The movement cost is 1 per step. If a person is adjacent to a door, they can exit in 1 second (provided that the door’s time slot is available). Even if multiple persons can reach the same door cell, only one person per door can exit in any given second.

The scheduling constraint can be formulated as follows: Suppose the shortest travel time for a person to reach a door is \(d\). Then that person can exit at any second \(t\) such that \(t \ge d\) (and \(t\) is an integer). Each door provides one exit opportunity per second.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of rows and columns). Each of the next \(N\) lines contains a string of length \(M\) representing a row of the grid. The grid contains only the characters ., X, and D with the conditions mentioned above.

outputFormat

Output the minimum number of seconds required to evacuate everyone safely. If it is impossible to evacuate all persons, output impossible (without quotes).

sample

3 3
DXD
...
DXD

2