题目描述

公主被恶人抓走，关押在牢房的某个地方。牢房用 $N \times M$（$N, M \leq 20$）的矩阵来表示。矩阵中的每个字符代表不同含义：

• @：道路，可以正常通行；
• #：墙壁，无法通过；
• x：守卫，需要花费额外时间杀死后才能继续前进；
• r：英勇的骑士，起始位置；
• a：公主，目标位置。

骑士每次可以向上、下、左、右四个方向移动，每移动一个位置需要 $1$ 个单位时间。当骑士遇到守卫时，必须杀死守卫才能继续前进，杀死一个守卫需要额外的 $1$ 个单位时间（即通过一个守卫总共需要 $2$ 个单位时间）。假设骑士足够强壮，有能力杀死所有守卫。

给定牢房矩阵，请你计算骑士成功到达公主所在位置需要花费的最短时间。如果无法到达，输出 Impossible。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示牢房的行数和列数。

接下来 $N$ 行，每行包含 $M$ 个字符，字符仅为 @、#、x、r、a 中的一种，表示牢房的布局。

输出格式

如果能够成功拯救公主，输出一个整数，表示行动所需的最短时间。

如果无法成功到达，输出 Impossible。

样例

7 8
#@#####@
#@a#@@r@
#@@#x@@@
@@#@@#@#
#@@@##@@
@#@@@@@@
@@@@@@@@

13

样例解释

骑士从 $(2,7)$ 出发，公主在 $(2,3)$。由于中间有墙壁阻挡，无法直接水平通过。一种最优路径为： $(2,7)\to(3,7)\to(3,6)\to(3,5)$（杀死守卫，花费 $2$）$\to(4,5)\to(5,5)\to(5,4)\to(5,3)\to(4,3)\to(3,3)\to(2,3)$。累计经过普通道路 $11$ 步，杀死守卫额外 $1$ 时间，总时间 $13$。可以证明这是最短时间。

数据范围与提示

对于 $100\%$ 的数据，$1 \leq N, M \leq 20$。矩阵中仅包含一个 r 和一个 a。