题目描述

给定一个最多 $100\times100$ 的 Sokoban 迷宫，恰好包含一个搬运工、一个箱子和一个目标格。

字符含义：

• #：墙；
• 空格：可通行格；
• @：搬运工初始位置；
• $：箱子初始位置；
• .：箱子的目标位置。

搬运工每次可以向上、下、左、右移动一格，不能穿墙。如果下一格是箱子，则只有当箱子前方一格可通行时才能推动箱子；箱子不能被拉动。

在所有能把箱子推到目标格的方案中：

1. 首先最小化推箱次数；
2. 在推箱次数最少的方案中，再最小化搬运工的总移动次数。

一次普通行走计一次移动，一次推动箱子同样计一次移动。

请只求出这两个最优值，不需要输出具体移动方案。

输入格式

输入为整个迷宫，所有行长度相同，行数和列数均不超过 $100$。迷宫外围保证封闭。@、$、. 各恰好出现一次。

输出格式

若无解，输出：

Impossible.

否则输出两个整数 $P,M$：

• $P$ 为把箱子推到目标格所需的最少推箱次数；
• $M$ 为在推箱次数恰好为 $P$ 的所有方案中，搬运工的最少总移动次数。

输入数据1

#######
#     #
#@$  .#
#     #
#######

输出数据1

3 3