Description

为了让奶牛们娱乐和锻炼,约翰建造了一个美丽的池塘。这个池塘是矩形的,可以分成M × N个方格。一些格子是坚固得令人惊讶的莲花,还有一些是岩石,其余的只是美丽、纯净、湛蓝的水。

贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花跳到另一朵莲花上,既不能跳到水里,也不能跳到岩石上。

贝西的舞步很像象棋中的马步:每次跳跃可以横移M1格,纵移M2格,或纵移M1格,横移M2格,最多有八个方向可供移动选择。

请计算贝西到达终点的最小步数,输入数据保证终点是一定可达的。

Input Format

第一行:四个用空格分开的整数:M,N,M1和M2,1 ≤ M, N ≤ 30,1 ≤ M1 ≤ 30,1 ≤ M2 ≤ 30,M1 ≠ M2

第二行到M + 1行:第i + 1行有N个用空格分开的整数,描述了池塘第i行的状态:0 为水,1 为莲花,2 为岩石,3 为起点,4 为终点。

Output Format

第一行:从起点到终点的最少步数

Sample

Input

4 5 1 2

1 0 1 0 1

3 0 2 0 4

0 1 2 0 0

0 0 0 1 0

Output

2

Hint

Hint

先跳到 1 行 3 列的莲花上,再跳到终点,需要 2 步

Source

USACO 2007 Feb