Last semester, a workshop on micromouse was organized. Inspired by that, the students of NITH decided to organize a fun event, wherein the micromouse was replaced by a blindfolded person. The winner of the competition will be the person who finds out the shortest part from the starting point to the centre of the maze.Your task is to list out the shortest path possible from the starting point to the centre of the maze. If there are multiple shortest paths, just list out any one of them.You will be given the dimensions of the 2-D maze
INPUT: First line contains, 1<= t<=10, the number of test cases, and then t test cases follow
The first line of each test case starts with two integers, n m, which is the size of the maze. The first cell is addressed as '0 0'
In the maze inaccessible cells are represented as '#' and the accessible cells are represented as '.'
The next line contains two pair of integers; first pair corresponds to the starting point and the second pair corresponding to the end point.
Then the maze of n x m size follows (see example).
OUTPUT: If there exists a path between the given starting and the end point, then output the address of each cell starting from the starting cell, in order to be followed to reach the end cell (see example). In case more than one path exists then output any of them.
In case no such path exists, output -1.