Geopeitus

In geocaching, the coordinates of a cache are sometimes given as a formula in which some digits have been replaced by letters, for example N58 24.1ab E26 44.3c.

Write a program that outputs every coordinate corresponding to the given formula together with the possible values of the variables.

The first line contains the formula. It consists of a latitude representation and a longitude representation; each representation is made up of a compass marker (N, S, E, W) followed by readings for degrees, minutes, and the fractional part of a minute. The length of the formula does not exceed 25 characters.

The second line contains the number of variables $N$ ($1 \le N \le 3$). Each of the next $N$ lines describes one variable: the variable name, an equals sign (=), and a comma-separated list whose elements are either single values or value ranges. A range is written as lo..hi and is inclusive of both endpoints (for example, 2..4 means 2, 3, 4). A variable name is always a single lowercase Latin letter. Values and range endpoints may be one- or two-digit integers. You may assume that no variable's description produces duplicate values.

Each occurrence of a variable's letter inside the formula is replaced textually by the decimal notation of the chosen value, so a two-digit value inserts two characters.

Output every coordinate that can be obtained by substituting the variables with their allowed values, one coordinate per line.

Because the output is compared byte-for-byte, print the coordinates in the following fixed order. Let the variables, in the order they appear in the input, be $v_1, v_2, \ldots, v_N$. Enumerate all combinations so that the first variable $v_1$ changes fastest (on every consecutive line) and the last variable $v_N$ changes slowest; equivalently, iterate $v_N$ in the outermost loop and $v_1$ in the innermost loop. Within a single variable, take its values in the order they are listed, expanding each range from its lower endpoint to its upper endpoint.