CODWRECK4 - Alien Language

no tags 

Aliens started their journey towards our earth. They some how mastered our English language through a dictionary. However, they were unable to understand the concept of spaces present between words.

They are continuously sending messages to our earth but it has to be converted to normal form (i.e if the aliens msg is helloworld it has to be translated into hello world with help of provided dictionary ). Scientist believes that these messages consist a very valuable information about how they planning to attack us. And it is guaranteed that aliens communicate only with the words present in the dictionary.

This small planet needs your help protect it with your skill

Warning!! very large input files use faster i/o's

Input

 

  • The first line of the input contains an integer N denoting the size of dictionary.
  • The next following N lines consist of words present in dictionary(all letters are lowercase)
  • The next line of the input contains an integer T denoting no.of alien language words that are need to be converted
  • See sample input and output for better understanding

 

Output

 

  • For each test case, output a single line which containing space seperated words that are present in the dictionary.
  • In case of multiple answers make sure the 1st word length to be minimum

 

Constraints

  • 1N105
  • 1|W|20
  • 1T100
  • 1|A|40
  • where |W| denotes the length of the largest string present in the dictionary and |A| denotes the length of the string from alien language

 

Example

Input:
6
coding
code
wreck
dechef
co
chef
2
codingwreck
codechef
Output: coding wreck co dechef

 


hide comments
Rishav Goyal: 2017-10-08 17:53:02

should be clear that there will be exactly 2 words in output.

wisfaq: 2017-10-07 15:17:31

Last edit: 2017-10-07 16:06:10
[Rampage] Blue.Mary: 2017-10-07 15:12:11

Last edit: 2017-10-07 15:24:44
[Rampage] Blue.Mary: 2017-10-07 15:11:32

Last edit: 2017-10-07 15:29:15
karthik_vg: 2017-10-07 15:09:31

time limit is improved :)


Added by:vg
Date:2017-10-07
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:VIIT-CodeWreck-Final-Round