Problem: Hunt-a-Word

Want to try solving this problem? You can submit your code online if you log in or register.

Hunt-a-Word

Input File: huntin.txt
Output File: huntout.txt
Time Limit: 0.333 second

A young friend has become quite interested in Hunt-a-Word puzzles, where one is given a rectangular block of letters, e.g.

XSMILEA
FHKDLDB
ISMIOQP
XDMFLGE
LSKLYEH

and asked to locate a word, such as DOG. In this example, DOG can be found beginning in row 2, column 4 and heading south-east (down and right).

Your friend is continually asking you for help on these puzzles, and you decide it would be good to write a program to help them and so allow you to concentrate on your school work.

Your task is to write a program which finds each word from a given list of words in a given block of letters. Note that words can occur more than once, in which case your program may find either occurrence. In the example above, the word SMILE occurs twice - once at row 1, column 2 and heading east, and once at row 5, column 2, and heading north-east.

Words may lie in any one of eight possible directions,

NW  N  NE
  \ | /  
   \|/   
W --+-- E
   /|\   
  / | \  
SW  S  SE

but must run in a straight line. For example, SMILE cannot be found at row 3, column 2 in the example above - it does not run straight in one of the eight possible directions.

Input

The first line shall consist of a pair of positive integers h w, separated by a single space, where h is the height (number of rows) of the block, and w is the width (number of columns) of the block. Each of h and w shall be at most 100.

Following this is the block of letters. There shall be exactly h lines, each consisting of exactly w characters and a single terminating newline. Each character shall be an upper case letter, from A ... Z inclusive.

Following this is a line with a single positive integer n, giving the number of words which need to be found in the grid. The integer n shall be at most 100.

Following this are n lines, each containing a word to be found on a single line together with a terminating newline. The word shall consist of at most 100 characters, each of which shall be an upper case letter, from A ... Z inclusive. Every supplied word shall occur at least once in the given block of letters.

Other than the space separating the integers h and w on the first line of input, there shall be no other space characters in the input file.

Output

You program shall output a sequence of finds, one to a line, where each find gives a location of a supplied word in the given block of letters. The finds shall be in the same order as the supplied words. In the event a word occurs multiple times in the grid, you should output only one location at which it is found (it does not matter which one).

A find shall consist of a two positive integers r c followed by a direction. The positive integers give the row (r) and column (c) in which the word starts. Both rows and columns are numbered so that the top left letter in the block is in row 1 and column 1. The direction shall be one of N, NE, E, SE, S, SW, W, NW in accordance with the compass diagram shown above.

Sample Input 1

5 7
XSMILEA
FHKDLDB
ISMIOQP
XDMFLGE
LSKLYEH
1
DOG

Sample Output 1

2 4 SE

Sample Input 2

5 7
XSMILEA
FHKDLDB
ISMIOQP
XDMFLGE
LSKLYEH
3
SMILE
DOG
ADO

Sample Output 2

1 2 E
2 4 SE
1 7 SW

Scoring

Your program will receive 100% for correctly locating one occurrence of each supplied word. Programs which do not correctly locate all supplied words shall receive proportionally less marks. For example, a program which correctly finds only 3 of 4 supplied words will receive 75%.

Note that the finds must be in the same order as the list of supplied words! If the finds are output in the incorrect order, they may not be legitimate finds of the corresponding word, and will not count as a correct find!