The Minotaur's Labyrinth

The labyrinth is a rectangular grid of equally sized square cells. Each cell is either empty (.) or blocked (#). The monster can move only between two empty cells that share an edge (up, down, left, or right) and can never step onto a blocked cell.

The entrance to the labyrinth is the top-left cell, and the monster's lair is the diagonally opposite bottom-right cell. Both cells are always empty, and initially there is a path from the entrance to the lair that walks only over empty cells.

You want to trap the monster by placing a single square-shaped obstacle in the labyrinth. Every cell the obstacle covers must be empty, and the obstacle may not cover the entrance cell or the lair cell. Once the obstacle is placed, the monster is trapped if no path from the entrance to the lair remains.

Find the size and position of the smallest square obstacle that can trap the monster.

The first line contains the width $w$ and height $h$ of the labyrinth, separated by a space. ($2 \le w, h \le 1500$)

Each of the next $h$ lines contains $w$ characters describing the map of the labyrinth. An empty cell is written as . and a blocked cell as #.

The entrance is the top-left cell $(1, 1)$, and the lair is the bottom-right cell $(w, h)$. Both cells are always empty, and a path from the entrance to the lair always exists.

Print three integers $l$, $x$, and $y$ separated by spaces. $l$ is the side length of the smallest square obstacle that traps the monster (removes every path from the entrance to the lair), and $(x, y)$ is the coordinate (column $x$, row $y$) of that obstacle's top-left cell. Every cell the obstacle covers must be empty, and it must not cover the entrance cell or the lair cell.

If several smallest obstacles are possible, print the one whose top-left cell has the smallest column $x$; if several share that column, print the one among them with the smallest row $y$.

If no single square obstacle can trap the monster, print Impossible.