Goal
In the classic game of Boggle you must look for words in a grid of 4 by 4 letters.
Valid words are formed by starting on any letter, then moving on to any horizontally, vertically or diagonally adjacent letter in the grid. Each cell of the grid may be used only once.
Your program is given a letter grid and a list of candidate words. For each word your program must output whether the word can be found in the grid.
Input
4 lines: the letter grid
1 line: N the number of words to check
N next lines: one word to check
Output
N lines: true if the word can be formed, false otherwise.
Example
Input
MPLR
DSDA
HNEO
SHTY
5
ARDENT
SHEAR
DOT
DEAD
YEAR
Output
true
true
true
false
true
