Background

《Minecraft》是一款沙盒类电子游戏，开创者为马库斯·阿列克谢·泊松（Notch）。游戏由Mojang Studios维护，现隶属于微软Xbox游戏工作室。 《Minecraft》拥有非常庞大的玩家社区，玩家可以将自己制作的地图上传至公开网络上供大家游玩。 大型迷宫曾经在《Minecraft》玩家社区中风靡一时，因其较低的制作难度，致使迷宫类地图随处可见。

Description

玩家Scenery下载了几张走迷宫的地图，但是走了很长时间都没能到达终点，于是他想通过作弊手段来完成迷宫。 他开启飞行来到迷宫正上方，并记录下了迷宫的样子、起点和终点。 然后回到起点按照正确的最短线来完成迷宫。 请你编写一个程序帮助他找到迷宫的最短路径。

Format

迷宫纵长m，迷宫横宽n，n*m的迷宫，起点坐标(sx,sy)，终点坐标(fx,fy)，经过的距离num。 其中，对于迷宫的表示：用 '#' 来表示墙壁；用 '.' 来表示可行走的部分；用 'O' 来表示行进路线。对于坐标的表示：规定左上角的点坐标为(0,0)。

Input

第一行输入 m，n。 接下来 m 行 n 列输入迷宫的具体样子。 第 m+2 行依次输入 sx，sy，fx，fy。

Output

第一行输出一个整数num。 接下来m行输出具体的行进路线。

Samples

5 5
# # # # #
# . # . #
# . # . #
# . . . #
# # # # #
1 1 3 1

7
# # # # #
# O # O #
# O # O #
# O O O #
# # # # #

50 29
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# . . . # . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# # # . # # # . # . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . #
# . # . . . . . # . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . # . # . #
# . # . # # # . # # # # # # # # # # # . # . # # . # # # # # # # # # # # # # # # # # # # . # . # . #
# . . . # . # . . . . . . . . . . . # . # . # . . . . . . . . . . . . . . . . . . . . # . # . # . #
# . # # # . # # # # # # # # # # # . # . # . # . # # # # # # # # # # # # # # # # # # . # . # . # . #
# . # . . . . . . . . . . . . . . . # . # . # . . . . . . . # . . . . . . . . . . # . # . . . # . #
# . # . # # # # # # # # # # # # # . # . # # # . # # # # # . # . # . # # # # # # . # . # # # # # . #
# . # . # . . . . . . . . . . . . . # . # . . . . . . . # . # . # . # . . . . # . # . # . . . # . #
# . # . # . # # # . # # # # # . # . # . # # # # # # # # # . # . # . # # # # . # . # . # . # . . . #
# # # . # . # . # . # . . . # . . . # . . . . . . . . . . . # . # . . . . . . # . # . # . # . # . #
# . # . # . # . # . # . # . # . . . # # # # # # # # # # # # # . # # # # # # # # . # . # . # . # . #
# . # . # . # . . . # . # . # . . . . . . . . . . . . . . . . . . . . . . . . . . # . # . # . # . #
# . # . # . # # # # # . # . # # # # # # # # # # # # # # # # # # # # # # # # # # # # . # . # . # . #
# . . . # . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . # . # . #
# . # . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . # . # . #
# . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . # . # . #
# . # . # # # # # # # # # # # # # . # # # # # # # # # # # # # # # # # # # . # # # # . # # # . # . #
# . # . # . . . . . # . # . . . # . # . . . . . . . . . . . . . . # . . . . . . . . . . . . . # . #
# # # . # . # # # . # . # . # . # . # . # # # # # # # # # # # # . # # # # # # # # # # # # # # # . #
# . # . # . # . # . # . . . # . . . # . # . . . . . . . . . . # . . . . . . . . . . . . . . . . . #
# . # . # # # . # . # . # . # # # # # . # # # # # # # # # # . # # # # # # # # # # # # # # # # # # #
# . # . . . . . . . # . # . . . . . # . # . . . . . . . . # . . . . . . . . . . . . . . . . . . . #
# . # # # # # # # . # . # # # # . . # . # . # # # # # # . # . # # # # # # # # # # # # # # # # # . #
# . . . . . . . . . . . . . . . . . # . . . # . # . . # . # . . . . . . . . . . . . . . . . . . . #
# # # # # # # . # # # # # # . . . . # # # # # . # . # # . # # # # # # # # # # # # # # # # # # # # #
# . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
1 1 48 27

186
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# O O O # . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . #
# # # O # # # . # . # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . #
# . # O O O O O # . . . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . # . # . #
# . # . # # # O # # # # # # # # # # # . # . # # . # # # # # # # # # # # # # # # # # # # . # . # . #
# . . . # . # O O O O O O O O O O O # . # . # . . . . . . . . . . . . . . . . . . . . # . # . # . #
# . # # # . # # # # # # # # # # # O # . # . # . # # # # # # # # # # # # # # # # # # . # . # . # . #
# . # O O O O O O O O O O O O O O O # . # . # . . . . . . . # . . . . . . . . . . # . # . . . # . #
# . # O # # # # # # # # # # # # # . # . # # # . # # # # # . # . # . # # # # # # . # . # # # # # . #
# . # O # . . . . . . . . . . . . . # . # . . . . . . . # . # . # . # . . . . # . # . # . . . # . #
# . # O # . # # # . # # # # # . # . # . # # # # # # # # # . # . # . # # # # . # . # . # . # O O O #
# # # O # . # . # . # . . . # . . . # . . . . . . . . . . . # . # . . . . . . # . # . # . # O # O #
# . # O # . # . # . # . # . # . . . # # # # # # # # # # # # # . # # # # # # # # . # . # . # O # O #
# . # O # . # . . . # . # . # . . . . . . . . . . . . . . . . . . . . . . . . . . # . # . # O # O #
# . # O # . # # # # # . # . # # # # # # # # # # # # # # # # # # # # # # # # # # # # . # . # O # O #
# . . O # . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . # O # O #
# . # O # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # . # O # O #
# . # O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O # . . . . . . # O # O #
# . # . # # # # # # # # # # # # # . # # # # # # # # # # # # # # # # # # # O # # # # . # # # O # O #
# . # . # . . . . . # . # . . . # . # O O O O O O O O O O O O O O # . . . O O O O O O O O O O # O #
# # # . # . # # # . # . # . # . # . # O # # # # # # # # # # # # O # # # # # # # # # # # # # # # O #
# . # . # . # . # . # . . . # . . . # O # . . . . . . . . . . # O O O O O O O O O O O O O O O O O #
# . # . # # # . # . # . # . # # # # # O # # # # # # # # # # . # # # # # # # # # # # # # # # # # # #
# . # . . . . . . . # . # . . . . . # O # O O O O O O O O # . . . . . . . . . . . . . . . . . . . #
# . # # # # # # # . # . # # # # . . # O # O # # # # # # O # . # # # # # # # # # # # # # # # # # . #
# . . . . . . . . . . . . . . . . . # O O O # . # . . # O # . . . . . . . . . . . . . . . . . . . #
# # # # # # # . # # # # # # . . . . # # # # # . # . # # O # # # # # # # # # # # # # # # # # # # # #
# . . . . . . . . . . . . . . . . . . . . . . . # . . . O O O O O O O O O O O O O O O O O O O O O #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

Limitation

0<m,n<=1000，1s，1024KiB for each test case.