Word Search using Trie

class Lief:
    def __init__(self, e, is_end):
        self.e = e
        self.children = {}
        self.is_end = is_end

    def add_child(self, e, is_end):
        self.children[e] = Lief(e, is_end)

    def get_child(self, e):
        return self.children[e]

    def remove_child(self, e):
        del self.children[e]

    def is_child(self, e):
        return e in self.children

    def has_children(self):
        return len(self.children) > 0

    def children_count(self):
        return len(self.children)

    def add_word(self, word):
        if word[0] not in self.children:
            # if letter not in children, create new lief
            new_lief = Lief(word[0], False)
            if len(word) > 1:
                new_lief.add_word(word[1:])
            else:
                new_lief.is_end = True
            self.children[word[0]] = new_lief
        else:
            self.children[word[0]].add_word(word[1:])

    def search_word(self, word):
        if word[0] == self.e:
            # if word initial matches lief
            if len(word) == 1 and self.is_end:
                return True
            elif len(word) > 1 and word[1] in self.children:
                return self.children[word[1]].search_word(word[1:])
            else:
                return False
        else:
            return False

    def remove_word(self, word):
        if word[0] == self.e:
            if len(word) == 1 and self.is_end:
                self.is_end = False
            elif len(word) > 1 and word[1] in self.children:
                self.children[word[1]].remove_word(word[1:])


class Trie:

    def __init__(self, wl=None):
        self.heads = {}
        if wl is not None:
            [self.add_word(word) for word in wl]

    def add_word(self, word):
        if not self.search_word(word):
            if word[0] not in self.heads:
                new_lief = Lief(word[0], False)
                if len(word) > 1:
                    new_lief.add_word(word[1:])
                else:
                    new_lief.is_end = True
                self.heads[word[0]] = new_lief
            else:
                self.heads[word[0]].add_word(word[1:])

    def search_word(self, word):
        if word[0] in self.heads:
            return self.heads[word[0]].search_word(word)
        else:
            return False

    def remove_word(self, word):
        if word[0] in self.heads:
            self.heads[word[0]].remove_word(word)

    def is_head(self, char):
        return char in self.heads

    def get_head(self, char):
        return self.heads[char]


# 0: right, rotation cc
direction = [
    (1, 0),         # 0: right
    (1, 1),         # 1: right down
    (0, 1),         # 2: down
    (-1, 1),        # 3: left down
    (-1, 0),        # 4: left
    (-1, -1),       # 5: left up
    (0, -1),        # 6: up
    (1, -1)         # 7: right up
]

d_name = {
    0: 'E',
    1: 'SE',
    2: 'S',
    3: 'SW',
    4: 'W',
    5: 'NW',
    6: 'N',
    7: 'NE',
}


def search_grid(g, trie: Trie):
    word_coors = {}
    found_words = []
    for y in range(len(g)):
        for x in range(len(g[0])):
            curr_char = g[y][x]
            if trie.is_head(curr_char):
                found_words += search_cell(g, x, y, trie.get_head(g[y][x]))
                if len(found_words) > 0:
                    for word in found_words:
                        word_coors[word] = (y+1, x+1)
                        dictionary.remove_word(word)
                    found_words = []
    return word_coors


def search_cell(g, x, y, node: Lief):
    found_words = []
    for d in range(len(direction)):
        found_words += search(g, x, y, d, node)
    return found_words


def search(g, x, y, d, node: Lief, words_found=None, word_str=''):
    if words_found is None:
        words_found = []
    global direction
    if node.e == g[y][x]:  # if current letter matches
        word_str += node.e

        if node.is_end:
            words_found.append(word_str)

        # increment step
        x += direction[d][0]
        y += direction[d][1]

        if 0 <= x < len(g[0]) and 0 <= y < len(g):  # check if next step is still within bounds

            next_char = g[y][x]

            if node.is_child(next_char):
                next_node = node.get_child(next_char)
                return search(g, x, y, d, next_node, words_found, word_str)
            else:
                return words_found

        else:
            # if next step is out of bounds
            return words_found
    else:
        return words_found


# [MAIN CODE]=======================================================================

# Get grid and word list
r, c = map(int, input().split())
grid = [input() for _ in range(r)]
word_count = int(input())
word_list = [input() for _ in range(word_count)]

# Cache words
dictionary = Trie(word_list)

# Search grid
word_coors = search_grid(grid, dictionary)
for word in word_list:
    print(*word_coors[word])

# [TEST CODE]=======================================================================

# grid = [
#         'xatnysnprabvbas',
#         'teehsdaerpslyug',
#         'soqgknsscoklpsn',
#         'ochmacaeceteeei',
#         'fyasarnprrrhfak',
#         'tjenngoascosprr',
#         'wjnkiewtohulsco',
#         'aexnteemsrowlhw',
#         'rbefrnprfietset',
#         'egiaeusecuritye',
#         'shhetcwhisasahn',
#         'ssrescriptwptku',
#         'xcremmapsryaurq',
#         'srevresavepmssq',
#         'socialwuevsuybb'
#         ]
#
# word_list = ['bar', 'engine', 'key', 'networking', 'save', 'scan', 'scanner', 'screen', 'screenshot', 'script',
#              'scroll', 'search', 'security', 'server', 'shareware', 'shell', 'shift', 'snapshot', 'social',
#              'software', 'spam', 'spammer', 'spreadsheet', 'spyware', 'status', 'storage', 'supercomputer',
#              'surf', 'syntax']
# dictionary = Trie(word_list)
# word_coors = search_grid(grid, dictionary)
# for word in word_list:
#     print('{}: {}'.format(word, word_coors[word]))