Find the words is a game. 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 = 12 and given the text

   WHEN LAST THE YOUNG ORLANDO PARTED FROM YOU 
    HE LEFT A PROMISE TO RETURN AGAIN 
    WITHIN AN HOUR, AND PACING THROUGH THE FOREST, 
    CHEWING THE FOOD OF SWEET AND BITTER FANCY, 
    LO, WHAT BEFELL! HE THREW HIS EYE ASIDE, 
    AND MARK WHAT OBJECT DID PRESENT ITSELF: 
    UNDER AN OAK, WHOSE BOUGHS WERE MOSS'D WITH AGE 
    AND HIGH TOP BALD WITH DRY ANTIQUITY, 
    A WRETCHED RAGGED MAN, O'ERGROWN WITH HAIR, 
    LAY SLEEPING ON HIS BACK: ABOUT HIS NECK 
    A GREEN AND GILDED SNAKE HAD WREATHED ITSELF, 
    WHO WITH HER HEAD NIMBLE IN THREATS APPROACH'D 
    THE OPENING OF HIS MOUTH; BUT SUDDENLY, 
    SEEING ORLANDO, IT UNLINK'D ITSELF, 
    AND WITH INDENTED GLIDES DID SLIP AWAY 
    INTO A BUSH: UNDER WHICH BUSH'S SHADE 
    A LIONESS, WITH UDDERS ALL DRAWN DRY, 
    LAY COUCHING, HEAD ON GROUND, WITH CATLIKE WATCH, 
    WHEN THAT THE SLEEPING MAN SHOULD STIR; FOR 'TIS 
    THE ROYAL DISPOSITION OF THAT BEAST 
    TO PREY ON NOTHING THAT DOTH SEEM AS DEAD: 
    THIS SEEN, ORLANDO DID APPROACH THE MAN 
    AND FOUND IT WAS HIS BROTHER, HIS ELDER BROTHER.

we obtain the following word-search matrix:

WOAHSAOGOTEAFIDETAUDITTARLNTENHWITHIDOIDDIUHLDNIUKHNTRTAOTDAADIE
HUREEIUTRHTNESMCINGWGHYGOAHHNAEIMSESDRNWGPSBIDDNNEAGIOISTHTNCFSL
ENTLTNRHEEACLEATTOHIHDAGWYIIAKDTBAOMELKILAHUOERGDWTMRYOTHSHDHOBD
NGEEOWARSFNYLYRDSASTTRWENSSSNEIHLPPONADTIWUSNRYHWATAFANTIEIOTURE
LODFRINOTODLHEKIEKWHOYRDWLBNDHTHEPEULNIHDANHESLEITHNOLOONESDHNOR
ARFTETDUCOBOEAWDLWEAPAEMIEAEGASEIRNTYDTIEYDSSAAATCESRDFPGMSIEDTB
SLRATHPGHDIWTSHPFHRGBNTATECCIDERNOIHSOSNSIESSLYDHHSHTITRTAEDMIHR
TAOPUILHEOTHHIARUOEEATCNHPKKLWLHTANBEIETDNRHWLCOCWLOISHEHSEAATEO
TNMRRNATWFTARDTENSMALIHOHIAADRFEHCGUETLEITWAIDONAHEUSPAYADNPNWRT
HDYONACHISETEEOSDEONDQEEANBGEEWARHOTIUFNDOHDTRUGTEELTOTOTEOPPAHH
EOOMANIENWRBWABEEBSDWUDRIGORDAHDEDFSNNADSAIEHACRLNPDHSBNDARRASIE
YPUIGHNFGEFEHNJNROSHIIRGROUESTONATHUGLNELBCAUWHOITISEIENODLONHSR

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

INPUT

Input will contain s, m, words[], n, lines[].

s - the skip value to use in doing the word search.

m - specifying the number of words to search for.

words[] - contain m words to search for, each string one word. 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.

n - number of lines in the search text.

lines[] - contain the search text. No String 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.

OUTPUT

Each String 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 OUT

¹ 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.

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

Definition:

Class:            WordSearch
Method:           find
Parameters:       String[]
Returns:          String[]
Method Signature: String[] find(int s, int m, String words[], int n, String lines[])

Discussion on Forum:

For all questions related to understanding of this challenge, please visit the forum at www.twincling.org/node/375

Please note that NO code or part of the solution will be discussed until the contest ends.