题目描述

小Z手上有一个大小为 $n\times m$ 的迷宫，迷宫的每一个格子都包含 $a,b,c$ 三种字母中的一个。

同时他手上还有一个长度为 $3$ 的字符串 $S_1S_2S_3$，也是由 $a,b,c$ 三种字母组成。

小Z 每次可以选中上下左右其中一个方向，并移动 $k$ 步 $(k\in {1,2,3})$，要求移动到的格子中的字母必须等于 $S_k$。每次移动之后，字符串要进行循环左移操作：$S_bS_cS_a\leftarrow S_aS_bS_c$

询问对于网格图中的每一个格子，按照以上要求移动到右下角 $(n,m)$ 的最少移动次数是多少。如果无法到达，输出 -1

输入格式

第一行，两个正整数 $n,m$，表示网格图的大小

第二行，一个长度为 $3$ 的字符串 $S_1S_2S_3$

接下来 $n$ 行，每行为长度为 $m$ 的仅由 $a,b,c$ 组成的字符串

输出格式

$n$ 行，每行 $m$ 个数字，第 $i$ 行，第 $j$ 列的数字表示该位置到达终点 $(n,m)$ 的最少移动次数，不可能的话输出 -1。

输入输出样例

3 4
abc
aabc
acaa
babc

2 -1 3 5
-1 2 5 3
1 -1 2 0

样例 $\tt \#1$说明

从方格 $(1,1)$ 出发，当前 $S=abc$；

向右移动 $3$ 格到达 $(1,4)$，当前方格为 c，$S_3=c$，移动完成后 $S$ 变为 bca；

向下移动 $2$ 格到达 $(3,4)$，当前方格为 $S_2=c$，移动完成后 $S$ 变为 cab。

从方格 $(2,4)$ 出发，当前 $S=abc$； 向左移动 $1$ 格到达 $(2,3)$，当前方格为 $a$，$S_1 =a$，移动完成后 $S$ 变为 bca；

向下移动 $1$ 格到达 $(3,3)$，当前方格为 $b$，$S_1=b$，移动完成后 $S$ 变为 cab； 向右移动 $1$ 格到达 $(3,4)$，当前方格为 $c$，$S_1=c$，移动完成后 $S$ 变为 abc。

1 9
aaa
aaaaaaaaa

3 3 2 2 2 1 1 1 0

7 4
aab
bbcb
ccba
cbbc
bbca
acbb
cacb
bcbb

4 -1 -1 -1
-1 -1 3 2
5 -1 -1 3
3 3 3 1
2 3 4 3
3 7 3 3
1 3 -1 0

数据范围

$50\%:n\times m\le1000$

另外 $10\%:S=xxx$ 并且所有格子都为 $x$

$100\%:1\le n,m\le 1000$