题目描述

周末放假回到了家，由于在学校很累，你很快的睡着了，做了一个神奇的梦，梦见你和平行时空的你被困在了一个n行m列的孤岛上。孤岛上含有平地，陷阱和传送门三种不同的地块。你和平行时空的你都可以上下左右移动到相邻的地块中，可是平行时空的你只能同时以相反的方向移动（即你和平行时空的你移动方向相反），两人均不能跨过孤岛的边界，即到达孤岛外的地方，并且任何人到达陷阱处会立即死亡，问你能否找到一个移动序列，使得两个人均能从传送门离开，其中一个人达到传送门后一定会离开孤岛不会再回来。如果你能够找到这样的移动序列，输出该序列的最短长度，否则输出-1。

输入格式

第一行输入四个整数n,m,x,y，表示n行m列的孤岛，初始两人在x行y列的地块中。

接下来n行，每行是一个包含m个字符的字符串，字符串仅包含 .#@ 三种字符，分别表示平地、陷阱和传送门。

数据保证两人初始时所在（x,y）位置是平地。

输出格式

如果能找到两个人离开的路径，输出该路径的最短长度，否则输出-1。

20%的数据保证：1<=n,m<=10

20%的数据保证：1<=n,m<=500

100%的数据保证：1<=n,m<=2e3,1<=x<=n,1<=y<=m

输入/输出例子1

3 3 2 2
@.@
#..
@.@

2

输入/输出例子2

1 3 1 2
..@

3

样例解释

对于样例二：两人初始在坐标（1,2），第一个人移动到（1,3）到达传送门离开，第二个人此时在（1,1），然后向右移动两次到达（1,3）离开，两人一共移动了3次。