该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小莹和香匙要去帮扭到腰的司令找墨水。可是她们身上所携带的墨水也不多了。幸运的是，全队的希望Agent3带够了墨水，重任自然交给了Agent3。

题目描述

现在有一张$n \times m$的地图，其中"O"代表可以到达的地点，"X"代表不可到达的地点（毕竟Agent3掉进河里就会爆炸）。Agent3可以从地图的一边看到另一边，但是她只能看东北，东，东南，南，西南……8个方向。如果Agent3能够看到墨水并且她到墨水的直线路径畅通无阻，那么她就可以直接冲刺拿到墨水而无需额外使用墨水。Agent3也可以向上下左右的任意一个相邻地点花费一格墨水喷墨，然后到达那一个地点。现在，请你帮她计算最少需要多少格墨水才可以获得补给。如果无论如何都不能到达，请你直接告诉她"Do not"。

输入数据

第一行输入两个数n和m

接下来n行，每行有m个字符，表示地图

接下来有多组测试数据，每行输入四个正整数，代表墨水的位置和Agent3的位置，以输入坐标值均为0表示输入结束。

输出数据

对于每一组询问，计算最小墨水消耗量，如果无法到达，输出"Do not",每问一行。

样例

样例1:

3 4
OXXO
XXOO
XOOO
3 2 2 4
3 3 1 1
0 0 0 0

1
Do not

样例2:

5 5
OOOOO
OOOOO
OOOOO
OOOOO
OOOOO
1 1 1 1
5 5 1 1
0 0 0 0

0
0

数据范围

请注意与平时不同的数据范围表达方式。

subtask0:对于10%的n和m，请输出样例1。

subtask1:对于30%的n和m,有$n\times m ≤ 100$。

subtask2:对于100%的n和m,有$n\times m ≤ 16384$，严格依赖subtask1。

询问最多有512组，保证Agent3和墨水不会在河里。