给你一个$n \times m$的矩形，#表示墙不能通过，S表示起点(可以通过)，.表示空地。你每次可以沿着上下左右四个方向移动。

问从S点出发，到达所有点最少需要移动多少次。

输入格式

第一行，两个整数$n,m$。

接下来$n$行，每行一个长度为$m$的字符串。

输出格式

一共$n$行$m$列，每个数表示移动到对应位置需要多少步，如果是墙或者无法到达，输出-1。

样例输入

5 5
.#.#.
.### .
..S#.
.##..
.....

样例输出

4 -1 -1 -1 12
3 -1 -1 -1 11
2 1 0 -1 10
3 -1 -1 8 9
4 5 6 7 8

数据规模

对于所有数据，保证$1\leq n,m \leq 200$，恰好有一个S。