beecrowd 3423 - Singular Tastes

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:

⌜: represents that if you are reading a word in the UP (U) direction, then you should change to the RIGHT (R) direction; or, conversely, if you are reading a word in the LEFT (L) direction, then you should change to the DOWN (D) direction; if you are already following direction R or D, then you should just continue in the current direction;
⌝: represents that if you are reading a word in direction R, then you should change to direction D; or, conversely, if you are reading a word in direction U, then you should change to direction L; if you are already following direction D or L, then you should just continue in the current direction;
⌟: represents that if you are reading a word in direction D, then you should change to direction L; or, conversely, if you are reading a word in direction R, then you should change to direction U; if you are already following direction L or U, then you should just continue in the current direction;
⌞: represents that if you are reading a word in direction L, then you should change to direction U; or, conversely, if you are reading a word in direction D, then you should change to direction R; if you are already following direction U or R, then you should just continue in the current direction.

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

beecrowd

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.

Input

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:

character 1 represents ⌜;
character 2 represents ⌝;
character 3 represents ⌟;
character 4 represents ⌞;

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 w_I, 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 w_I's never exceed 1.5 × 10⁴.

Output

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

the string "I J C" (1 ≤ I ≤ N; 1 ≤ J ≤ M; C ∈ {D, L, R, U}), without the quotation marks, representing that word w_I can be found in the grid starting at position (I, J) following direction C, not being the character at position (I, J) a special symbol;
the string ":(", without the quotation marks, representing that word w_I cannot be found in the grid.

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

Input Sample	Output Sample
5 9 1ISTI21N2 RERAZAITG HY2SAN3RU C4R4TESAL AR4EVKO43 6 CHRISTIAN TASTES ARE VERY SINGULAR X	4 1 U 1 4 D 2 4 L 5 5 L 4 7 U :(