题目描述

为了让奶牛们娱乐和锻炼，Farmer John 建造了一个美丽的莲花池。池塘被划分成 $M$ 行 $N$ 列的方格，其中一些格子有莲花，一些格子是岩石，其余格子是水。

贝西站在一朵莲花上，想跳到另一朵指定的莲花。她只能落在莲花上，不能落入水中，也不能落在岩石上。

贝西每次跳跃的方式类似国际象棋中的马步：她可以先在一个方向移动 $M_1$ 格，再在与其垂直的方向移动 $M_2$ 格；也可以交换 $M_1$ 和 $M_2$。因此最多有八种不同的跳跃方向。

请计算贝西从起点跳到终点所需的最少步数。输入保证终点一定可以到达。

输入格式

第一行包含四个整数 $M,N,M_1,M_2$。

接下来 $M$ 行，每行包含 $N$ 个整数，表示池塘的状态：

• $0$ 表示水；
• $1$ 表示莲花；
• $2$ 表示岩石；
• $3$ 表示贝西的起点；
• $4$ 表示贝西的终点。

输出格式

输出一个整数，表示从起点到终点的最少跳跃次数。

样例

输入

4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0

输出

2

数据范围

$1\le M,N\le 30$，$1\le M_1,M_2\le 30$，并且 $M_1\ne M_2$。

4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0

2

4 5 2 1
1 1 1 1 1
1 1 1 1 1
1 3 1 1 1
1 1 1 1 4

2

6 4 2 1
1 4 1 3
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

2