Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Deduction
 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 640 Accepted: 206

Description

S is a set of 52 declarations, which is represented by lower case letters ('a', 'b', ..., 'z') and upper case letters ('A', 'B', ..., 'Z'). These declarations are not completely independent with each other, And from some of them, we can deduce some others. We denote this relation as "=>". For instance, a => b means from declaration a, we can deduce declaration b; b => c, means from declaration b, we can deduce declaration c. And from a => b and b =>c, we can also get a => bc, which means from a, we can deduce both b and c. Let's see some further examples: abc => de means from a, b, and c, we can deduce d and e. bc => fgh means from bc, we can deduce fgh. And from abc => de, bc => fhg, we can finally get abc => defgh, even more, we can get abc => abcdefgh.

Now given m deduction relations, which are represented in the form S1 => S2, S1 and S2 are subsets of S, and n queries, each contains a subset Q of S. Your job is to find all declarations can be deduced from Q according to the given relations.

Input

Input will contain m + n + 1 lines. The first line contains two positive integers m, n. (m is less than 200, and n is less than 1000). Then m lines follow, each with a deduction relation. The last n lines each contains a query.

You can see that there is no space between declarations in S1, S2 and Q. And there is one space between S1 and "=>" and between "=>" and S2. And it is confirmed that the number of declarations in S1, S2 and Q will not exceed 52.

Output

For each query, output the answer for the query. The element for the output should be in the order [a, b, c, ..., y, z, A, B, C, ..., Y, Z].

Sample Input

```2 1
abc => de
bcb => FGh
abc
```

Sample Output

`abcdehFG`

Source

[Submit]   [Go Back]   [Status]   [Discuss]