Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Deduction
Time Limit: 1000MSMemory Limit: 10000K
Total Submissions: 600Accepted: 183

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]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator