JS Minification

Time limit2sMemory limit512 MB

Summary

Given JS-like source lines and a reserved token list, rename words to a, b, ... in first-use order and print one line with the fewest spaces.

Level: Medium5 of 10
Topics: String, Simulation, Implementation
Solved: No attempts yet

Problem

International Coding Procedures Company (ICPC) writes all its code in Jedi Script (JS). JS is not compiled. Its source is delivered for execution in source form. Sources contain comments, extra whitespace (including leading and trailing spaces), and other elements that make them large without changing their meaning. Before delivery, ICPC minifies each source file to shrink it while keeping its meaning.

ICPC follows strict practices, so its JS grammar is restricted. The code handles only integer algorithms. It uses no floating point numbers and no strings.

Each source is a sequence of lines. A line holds zero or more tokens separated by spaces. On each line, the part that starts at a hash character (#, ASCII 35) and runs to the end of the line is a comment and is ignored.

Each line is parsed from left to right. At each position, skip spaces, then take the longest token that starts there. The token types are:

Reserved token: an operator, separator, literal, reserved word, or library function name that minification must keep. A reserved token is a fixed string of non-space ASCII characters with no hash character. All reserved tokens are given as input.
Number token: a sequence of digits from 0 to 9.
Word token: a sequence of lowercase letters, uppercase letters, digits, underscore (_, ASCII 95), and dollar sign ($, ASCII 36). A word does not start with a digit.

If the longest string that matches a number or word definition is in the reserved token list, it counts as a reserved token.

Words are renamed in a fixed order:

The target word list contains the words made only of lowercase letters, sorted by length and then lexicographically: a, b, ..., z, aa, ab, ... Reserved tokens are excluded.
The first word that appears in the input token sequence is renamed to the first target word, and every later occurrence of it is renamed too. The second new word gets the second target word, and so on.

The goal is to produce one line with the fewest spaces that parses to the same token sequence with the renamed words.

Input

The first line contains an integer $n$ ( $0 \le n \le 40$ ), the number of reserved tokens.

The second line contains the reserved tokens separated by spaces, with no repeats. Each token is 1 to 20 characters long and uses only ASCII codes 33 to 126, excluding the hash character.

The third line contains an integer $m$ ( $1 \le m \le 40$ ), the number of source lines.

The next $m$ lines contain the source. Each line is at most 80 characters long, counting leading and trailing spaces, and uses only ASCII codes 32 to 126. The source is valid and parses fully into tokens.

Output

Print one line: the minified source. It must parse to the same token sequence as the input, with the words renamed as described, and it must contain the fewest spaces possible. If several outputs use that minimum number of spaces, print any one of them.

Examples2

Example 1

Input

16
fun while return var { } ( ) , ; > = + ++ - --
9
fun fib(num) { # compute fibs
  var return_value = 1, prev = 0, temp;
  while (num > 0) {
    temp = return_value; return_value = return_value + prev;
    prev = temp;
    num--;
  }
  return return_value;
}

Expected output

fun a(b){var c=1,d=0,e;while(b>0){e=c;c=c+d;d=e;b--;}return c;}

Example 2

Input

10
( ) + ++ : -> >> >>: b c)
2
($val1++ + +4 kb) >> :out
b-> + 10 >>: t # using >>:

Expected output

(a+++ +4c )>> :d b->+10>>:e