5852 - 等级6:逃离迷宫

通过次数

2

提交次数

2

Time Limit : 1 秒
Memory Limit : 128 MB

小A和小B被困在一个包含空地".",陷阱"#",传送阵"@"的迷宫,他们可以上下左右任意移动,但是他们的行动是相反的,即小A向上,则小B向下,问你2人都离开迷宫时,最少需要几步?注意的时其中1个人到达传送阵时,那么他就离开,另一个则还需要继续走,如果进入陷阱,代表失败,若无法离开则输出-1

Input

输入包含n+1 行:
第一行输入四个整数n,m,x,y(1≦n,m≦2×10^3 ; 1≦x≦n; 1≦y≦m);
接下来n 行,第i 行输入一个长度为m 的字符串si ,仅由 `.`、`#`、`@` 组成,描述第i 行的地形。
保证起点(x,y) 处为平地。

Output

若存在可行方案,输出最短移动步数;否则输出−1。

Examples

Input

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

Output

2

Input

1 3 1 2
..@

Output

3

Input

3 1 2 1
#
.
@

Output

-1

Hint

样例1 一个可以先往上后往左到达(1,1)传送门 另外一个会先下后右到达(3,3)传送门