Solving Sõnasnäkk
InterviewTime limit1sMemory limit1024 MB
Given a list of available letters and allowed words, print each word that can be spelled using the letters, using each letter at most once, in input order.
Problem
Sõnasnäkk is a game where you form words from a given set of letters. Write a helper program that takes the list of available letters and the list of allowed words, and finds which allowed words can be formed from the available letters.
Input
The first line contains the list of available letters. Each letter is a lowercase English letter from 'a' to 'z', and the list has between 1 and 100000 letters.
The second line contains the number of allowed words (). Each of the next lines contains one allowed word. Words consist of lowercase English letters only, and each has a length between 1 and 100000. In every test, the sum of the lengths of the allowed words does not exceed 1000000.
Output
Print the allowed words that can be formed from the letters on the first line, in the order they appear in the input, one per line.