Not an official ACM page
[Problem 5 | 1997 East-Central problem set | Ed's programming contest problem archive | my home page]

ACM East Central Region
1997 Regional Programming Contest

Problem 4 - Word Search

Wonder Word search is a game enjoyed by all ages. The basic idea is to find certain specified words within a given matrix of letters.

One interesting means of constructing a word search matrix is to take some written text (in upper case), strip out all but the characters A - Z, and format the resulting sequence of characters into columns of s characters. That is, taking s = 9 and given the text

Our revels now are ended. These our actors,
As I foretold you, were all spirits and
Are melted into air, into thin air:
And, like the baseless fabric of this vision,
The cloud-capp'd towers, the gorgeous palaces,
The solemn temples, the great globe itself,
Ye all which it inherit, shall dissolve
And, like this insubstantial pageant faded,
Leave not a rack behind. We are such stuff
As dreams are made on, and our little life
Is rounded with a sleep.

We obtain the following word-search matrix: 

ONERIYLNEIITSFODEGCESGLHEDNSNAEAWSEDRFEE
UODAFOSDDNRHSTNCREEMTLFIRIDITNACETAELEDE
RWTCOUPAITAEFHTASOSNHOYCISLNITVKAUMOIIWP
RAHTRWIRNONBAIHPTUTTEBEHTSISAFEBRFSNTSI
EREOEERETTDABSEPHSHEGEAISOKULANEEFAATRT
VESRTRIMOHLSRVCDEPEMRIATHLEBPDOHSARNLOH
EEESOETEAIIEIILTGASPETLIAVTSAETIUSEDEUA
LNOALASLINKLCSOOOLOLASLNLEHTGDANCDMOLNS
SDUSDLATRAEEOIUWRALETEWHLAIAELRDHRAUIDL

We can now search this matrix for words. For example, the word "SAFE" can be found starting at lexicographic position 246 and running eastward in the text. 3 Since, running row-wise, we are looking at every s'th character, the value of s is sometimes called a skip value.

For this problem, you will be given search words, a search text, and a skip value. Your job (well, really, your program's job) is to find the location of each of the search words within the search text, formatted into a search matrix according to the given skip value.

Input

The first line of input will contain a single integer specifying the skip value to use in doing the word search. The second line will contain a single integer m specifying the number of words to search for. The next m lines will contain the words to search for, one word per line. The words will be given in all uppercase. No word will be more than 32 characters in length. There will be a maximum of 128 search words. After the search words will be a line containing a single integer n giving the number of lines in the search text. The next n lines contain the search text. No line of search text will be more than 128 characters long. All characters in the text will be upper case. There will be a maximum of 5452 lines. 4

Output

Each line of output should contain a search word, the lexicographical location of the first character of the word in the search text, and its orientation (the direction in which the rest of characters are oriented with respect to the first character). Valid directions are N, NE, E, SE, S, SW, W, and NW, indicating text running in the corresponding directions within the word search text matrix. If a word occurs more than once in the search matrix, you should print out only the location of its first occurence. The words in the output should be ordered as given in the input. Each line of output should contain the search word, followed by a space, then the lexicographic position of the word, followed by another space, and finally the direction that word runs in the search text. If a word is not found in the search matrix, the line should contain the word followed by a space and then the text 

NOT FOUND

3 By lexicographic position we mean the numerical position with the search matrix when counting consecutively and column-wise from the first character, which is position 0.
4 The number of lines in Hamlet.

Sample Input

9
5
SAFE
TOES
SHAKE
SPEARE
GLOBE
11
OUR REVELS NOW ARE ENDED. THESE OUR ACTORS,
AS I FORETOLD YOU, WERE ALL SPIRITS, AND
ARE MELTED INTO AIR, INTO THIN AIR:
AND, LIKE THE BASELESS FABRIC OF THIS VISION,
THE CLOUD-CAPP'D TOWERS, THE GORGEOUS PALACES,
THE SOLEMN TEMPLES, THE GREAT GLOBE ITSELF,
YEA, ALL WHICH IT INHERIT, SHALL DISSOLVE,
AND, LIKE THIS INSUBSTANTIAL PAGEANT FADED,
LEAVE NOT A RACK BEHIND. WE ARE SUCH STUFF
AS DREAMS ARE MADE ON; AND OUR LITTLE LIFE
IS ROUNDED WITH A SLEEP.

Output for the Sample Input

SAFE 246 E
TOES 85 SW
SHAKE NOT FOUND
SPEARE NOT FOUND
GLOBE 189 S
This page maintained by Ed Karrels.
Last updated December 10, 1999