Tank Battle

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

       When WAVwind is writing AI for Turing Cup, he comes across a problem: a tank is a square of four units in the map. He knows both positions of his and the enemies’ tank, also, he know the information of the whole map. WAVwind want to approach the enemies’ tanks as soon as possible, but because of the actions of enemies being unsure, he suppose their tanks are static. Please find the minimum steps of the way from present location to the enemy’s location and the direction which should be selected if you choose the minimum way.(“UP” represents moving up, “DOWN” represents moving down, “LEFT” represents moving left, “RIGHT” represents moving right.If  the  direction is  nonunique ,print the one which is the max("UP">"DOWN">"LEFT">"RIGHT" ) ). Attention please, the tank can only moves up, down, left, right only one unit.

Input

The fist line is the case number. For each case, the first line contains two integers n, m, where n represents row and m represent column (10<=n,m<=20). The followed line is a n*m matrix, 1 represents blank area that the tank can move on it, 0 represents river or brick that the tank can not get across. The final 4 integers x1,y1,x2,y2 mean the coordinate of WAVwind’s tank (x1,y1) and the enemy’s tank (x2,y2).(The coordinate is the top left position of the tank, we ensure that the input are all validate, which means no two tanks has the same coordinate ).

Output

Output the minimum steps from self to the enemy, following a line represents the first direction to move.Print a word “fail” if there is no way.

Sample Input

2
4 4
1111
1111
1111
1111
0 0 2 2
4 6
110011
111111
110011
111111
2 0 0 4

Sample Output

4
DOWN
fail

Hint

Source

NJUSTACMCONTEST--WAVwind

提交代码