走迷宫 3144

Time Limit: 1 s Memory Limit: 256 MB

Submission：14 AC：3 Score：0

Description

现有一个 n×m 的迷宫矩阵 maze，矩阵中有空格子（用1表示，可通行）和墙（用0表示，不可通行），在迷宫中通行的每一步移动操作，你必须以上，下，左或者右方向移动一个格子（不能进入墙所在的格子）。你的目标是找到离入口最近的出口，并规划入口到出口的行走路径。（出口的含义是 maze 边界上的空格子。入口格子不算出口）。如果不存在这样的路径，请你返回-1；如果有，则展示入口到出口的行走路径。

Input

第一行有n和m两个数（1≤n,m≤1000），表示迷宫有n行m列。

第二行有a和b两个数（1≤a≤n，1≤b≤m），表示入口在第a行第b列。

接下来有n行，每行有m个数字为x_i,j，代表该位置的格子能否通过。

Output

第一行输出最近出口位置和最少移动步数

接下来n行输出最终的走法，墙壁为0，不经过的空格子用2表示，经过的空格子用"."表示（没有引号），若没有走法，则输出-1。

Samples

input

10 10 1 0 0000000010 1110111010 0110111011 0111100110 0100011110 0111011110 0101110110 0100010000 0011111111 0001000000

output

9 3 15 0000000020 ..20222020 0.20222022 0.22200220 0.00022220 0...022220 020...0220 02000.0000 002...2222 000.000000

Hint

测试点缺少