You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

土拨鼠 乐乐 下载了一个游戏《冰与火》👀️

Description

游戏是这样的：

给出一张 $n \times m$ 的地图，地图上有冰也有火，每块冰或火在每一个 $1 \times 1$ 的方格中，互不干涉。

现在 乐乐 会被系统随机分配到 $n \times m$ 的地图中的 $(x1,~y1)$ 点上，这个点可能是冰，也可能是火。

乐乐会得到一双靴子，这双靴子可以避免冰和火中其中一者的伤害。具体避免什么取决于这个随机分配的点是冰还是火。

例如下图：

乐乐 被随机分配到了 $(3,~5)$ 点，那么他就获得到一双可以防火的靴子，他就可以在 $(1,~1),~(1,~6),~(2,~2),~(2,~4),~(2,~7),~(3,~3),~(3,~5),~(3,~6),~(4,~2)$ 点上停留，但其余冰点不可触碰。

游戏规则为可以从当前点出发走向与之相邻的8个点。同时，乐乐 作为新手玩家，系统给予了 乐乐 一个技能 $x$。$x$表示可以从当前点出发，可以走向与当前点的距离等于 $x$ 的点。当然，这些所有的点必须是这双靴子可以免伤的点。

于是，乐乐 可以走到的点分别是（假设当前点为 $(i,~j)$）：

$(i-1,~j-1),~(i-1,~j),~(i-1~j+1),$

$(i,~j-1),~~~~~~~~(i,~j),~~~~~~~~(i,~j+1)$

$(i+1,~j-1),~(i+1,~j),~(i+1,~j+1)$

$(i-x,~j-x),~(i-x,~j),~(i-x,~j+x),$

$(i,~j-x),~~~~~~~~~~~~~~~~~~~~~~~~~~~(i,~j+x)$

$(i+x,~j-x),~(i+x,~j),~(i+x,~j+x)$

乐乐 能走到的点为以上点中在地图上的点。

再例如下图：

乐乐 被随机分配到了 $(3,~5)$ 点，他获得到一双可以防火的靴子。若 $x~=~2$，那么他的第一步就可以走到 $(2,~4),~(3,~3)$ 或 $(3,~6)$。

游戏会有一个宝藏藏在 $(x2,~y2)$ 点上。请你告诉乐乐，他能不能走到宝箱。并请你告诉他最短的路径经过了几个点。

Format

Input

第1行为7个整数 $n,~m,~x1,~y1,~x2,~y2,~x$。

接下来 $n$ 行，每行 $m$ 个 01 数，表示这张地图。其中 0 表示冰，1 表示火。

Output

若能走到，输出最短的步数。否则输出 Oh,poor me!。

Samples

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

2

【Sample 1】说明：

乐乐 可以按照这样的脚步前进：

5 5 1 1 5 5 2
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 0 1

Oh,poor me!

Limitation

对于 $30\%$ 的数据，$n,~m \le 20$；

对于另外 $20\%$ 的数据，$n,~m \le 10^2$；

对于 $100\%$ 的数据，

$n~,m \ge 4$

$1 \leq x1,~x2 \leq n \leq 10^3$

$1 \leq y1,~y2 \leq m \leq 10^3$

$2 \leq x \leq \displaystyle \lfloor \frac{\text {min}(n,~m)}{2} \rfloor$