beecrowd | 3423

Singular Tastes

By Leandro Zatesko BR Brazil

Timelimit: 12

Christian loves to do word searches. However, his tastes are very singular, and he only does word searches from The Singular Magazine. A word search from The Singular Magazine is an N × M grid followed by a list of Q words that you must find in the grid. Words consist only of capital English letters and can be found in the grid in vertical or horizontal directions. Diagonals are not considered.

So far, nothing singular concerning this word search. However, some cells of the grid can be special. A special cell consists of one of the following special symbols, which should not be part of the word that is being read:

The figure below depicts the word CHRISTIAN being found in a 5 × 9 grid.


Anna is the maganize's employee that creates the grid every week, and Bob is the employee that creates the word list. However, the words in Bob's list always contain the special symbols if they appear while reading the words chosen. It is the editor of the magazine who deletes the special symbols from the word list after Anna and Bob conclude their tasks. If a word happens to be empty in this deletion process, that word is then simply ruled out of the word list.

A grid created by Anna is said to be cyclic if, for every positive integer K, Bob can add a word of length at least K to his list, if he wants to (even if such word contains only special symbols). The Singular Magazine guarantees that the word searches published have never cyclic grids. It is also guaranteed that there is at least one cell of the grid which is not special.


The first line of the input consists of two positive integers N and M (N, M ≤ 200). The next N lines, each consisting of M characters, contain the description of the N × M grid. English letters in the grid are represented by themselves, whilst the special cells are represented as follows:

After the description of the grid, a line consisting of a positive integer Q follows. Then, each I-th of the next Q lines consists of the word  wI, that is, a non-empty string which represents the I-th word of the list that must be found in the grid, as published by the editor of The Singular Magazine. The sum of the lengths of all wI's never exceed 1.5 × 104.


Print Q lines, the I-th of which must be of one of the following forms:

If two or more distinct strings serve as the solution for some word wI, print the lexicographically smallest (treating the digits of numbers I and J as ASCII characters).

Input Sample Output Sample

5 9

4 1 U
1 4 D
2 4 L
5 5 L
4 7 U