Consider a grid map of size m×n. The origin (0, 0) is taken as the top-left corner. The X axis is the vertical axis, the Y axis is the horizontal axis. A cell 0 denotes obstacle-free region, -1 denotes obstacles, and 1 denotes a gem. Given a source, the aim of the agent is to go to the gem. The step cost is the time. The agent moves 1 block distance per second (or √2 time for diagonal moves). The order of preference of actions is: E, SE, S, SW, W, NW, N, NE, where N, E, S, W stand for North, East, South and West respectively. Print the path from the source to the gem using Iterative Lengthening. Print only -1 if no path exists.

The input is t, the number of test cases, followed by (for every test case) m and n. The next m lines of n integers each denote the grid map. The next line contains the source indicated by two integers Sx Sy. The output is the path.

Take ε as 1. 1≤m,n≤100