Swap the Robots

あなたは、Boston Dynamicsに対抗しようとしているスタートアップで働いています。ここでの課題の一つは、2台のロボットが互いに重ならないように場所を入れ替えることです。

グリッドの高さは h、幅は w で、床はドット（.）、壁はハッシュ（#）で表されています。

ロボットは、隣り合うマスに対して水平方向、垂直方向、そして斜め方向に動くことができます。ただし、互いの位置や壁の上に乗ることは禁じられています。各ステップでは、両方のロボットが1マス動くか、動かずに留まるかを選べますが、同じタイミングでお互いを飛び越えるような動きはできません。

最初のロボットを2番目のロボットがいた場所へ、そして2番目のロボットを最初のロボットがいた場所へ移動させるために必要な最小ステップ数を求めます。もし移動が不可能なら「Impossible」とします。

入力の最初の行には2つの整数 h と w が与えられ、(1 ≤ h, w ≤ 50) を満たします。

続く h 行には、幅 w の文字列が記されており、床と壁の情報が含まれています。

1台目のロボットは文字 A、2台目のロボットは文字 B で示されています。

ロボット同士を入れ替えるのに必要な最小ステップ数を出力し、もし不可能な場合は Impossible と出力してください。

Input

4 4
AB.#
###.
...#
.###

Output

11

Input

2 2
AB
..

Output

2

Input

1 3
A.B

Output

Impossible