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 (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). 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 the input is an integer K, then a blank line followed by K datasets. There is a blank line between datasets. The first line of each dataset contains 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
2/2 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 (the number of lines in Hamlet). 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’, in that order of precedence, 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 with the lowest lexicographical position of the first letter. 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’. Print a blank line between datasets. Sample Input 1 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. Sample Output SAFE 246 E TOES 85 SW SHAKE NOT FOUND SPEARE NOT FOUND GLOBE 189 S