Woburn Challenge 2001

Losing the office pools would be an intelligence failure that would certainly cost M her job as chief of MI6. Resorting to means employed during the cold war, she decides to take action on several fronts. She decides to foment a revolution on Survivor Island to kick out the current dominant player and install her choice (Amber) as the winner of Survivor. She quickly deploys John Patrick Mason (a crack commando of the Special Air Service, SAS), a veteran of inserting onto ex-prison islands (his last mission was on Alcatraz). His job would be to infiltrate Survivor Island (Australia) and take the necessary measures to ensure that the "right" contestant would win.

Mason paradrops onto the island at night at a designated coordinate and inexplicably blurts out to no one in particular, "Welcome to the Rock." He has been provided with a rather strange map to the main camp. At each coordinate on the map, a number is listed $(1-9)$, that encodes the direction that he must next travel from that coordinate to reach the next coordinate. Note that the map was prepared by P, who isn't always sound of mind, and thus it might turn out that the directions given would lead him to fall off the island or go in circles (and since it is pitch-black he can't tell if he's about to fall off the island).

Consider the island to be an $N$ by $N$ grid with each coordinate labelled with an ASCII character. The map consists of an $N$ by $N$ grid with each coordinate labelled with a number from $1-9$ $(N=8,NE=9,E=6,SE=3,S=2,SW=1,W=4,NW=7)$, as shown below in Figure 1, indicating the direction to travel. Please note that $5$ will never appear in the input, and does not correspond to any direction. Your job is to report the grid coordinates that John travels (i.e. a string of ASCII characters). If there is a circular path, report it. If he falls off the island, that is the end of the path.

Figure 1

Input Specification

The first line contains $N$, the size of the grid $(1\le N\le 100)$ and $T$, the number of test cases (starting positions). The next $N$ lines show the labels of the island grid (each line contains $N$ characters). The next $N$ lines similarly show the directions on the grid that Mason should follow. The remaining $T$ lines will each contain a test case in the form $R,C$ $(1\le R,C\le N)$, the row and column that Mason is to start at ($1,1$ would be the northwest corner, $N,N$ would be the southeast).

Output Specification

For each starting position, describe the path that Mason follows by outputting the labels of the positions he walks along in the format shown below.

Sample Input

5 5
ABCDE
GGHIJ
LLMNO
GQRST
UVWXY
96666
32222
91222
89222
94444
1 1
1 2
2 5
3 3
2 1

Sample Output

A
BCDE
JOTYX then WVUQMR repeated
MRWVUQ repeated
G then LGLG repeated

Note: We are interested in knowing about how the path loops, not how the ASCII string loops: so for the fifth sample test case, GL repeated, G then LG repeated, GLGL repeated, and G then LGLGLGLG repeated would all be wrong.