Word Search in a Grid

You are given a 2D grid of uppercase letters and a list of words. Your task is to determine for each word whether it exists in the grid. A word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells include horizontal, vertical, and diagonal neighbors. Each cell can be used at most once for constructing a word.

Formally, given a grid (G) of size (n \times m) and a word (w) of length (L), there exists a sequence of coordinates ((i_0, j_0), (i_1, j_1), \dots, (i_{L-1}, j_{L-1})) such that for all (0 \le k < L), (G[i_k][j_k] = w[k]) and for any two consecutive coordinates, the cells are adjacent, i.e., [ |i_k - i_{k+1}| \le 1 \quad \text{and} \quad |j_k - j_{k+1]| \le 1. ] Note that the same cell cannot be reused in the construction of a single word.

Your program should read the grid and the list of words from standard input, check each word, and output a JSON formatted dictionary mapping each word to a boolean value (true if the word is found, false otherwise).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers, (n) and (m), representing the number of rows and columns in the grid.
• The next (n) lines each contain (m) uppercase letters separated by spaces, representing the grid.
• The next line contains an integer (w) representing the number of words to search for.
• The following (w) lines each contain a word (a string of uppercase letters).

For example:

3 4 A B C E S F C S A D E E 3 ABCCED SEE ABCB

outputFormat

The output is printed to standard output (stdout) as a JSON formatted dictionary. The keys are the words provided in the input, and the corresponding values are booleans: true if the word can be found in the grid and false otherwise.

For example:

{"ABCCED": true, "SEE": true, "ABCB": false}## sample

3 4
A B C E
S F C S
A D E E
3
ABCCED
SEE
ABCB

{"ABCCED": true, "SEE": true, "ABCB": false}