ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1257. Hyphenation

Time limit: 1.0 second
Memory limit: 64 MB
Programmers are strange people. They don’t want to rejoice in life's pleasures, to read books, to listen to the music, to write letters to each other. The code, debug, rebuild something all the time. So our acquaintance programmer Vasechkin is not pleased with the existing software. This time he rages against the text editor. This editor can’t carry words over to the next line. What can a man do? Artemy Sidorovich, seemingly, is to teach this editor do this.

Input

The first line contains integer N (0 ≤ N ≤ 100) — an amount of hyphenation rules. Then there are N lines with the rules description. Each rule looks like “string1-string2”, where string1 and string2 are not empty and contain only small and capital Latin letters. Summary length of string1 and string2 does not exceed 40 symbols. This record means that if a word is ended with a substring string1string2, then string2 may be carried to the next line and after string1 appears a hyphen-mark ‘-‘. Then there is a text typed by Artemy Sidorovich. A word is a sequence of small and capital Latin letters. Any other symbols are word separators. Each line is not longer than 250 symbols. The text consists of not more than 450 lines. Each word is not longer than 40 symbols.

Output

Output a text formatted according to the hyphenation rules with respect to the fact that the paper width is 40 symbols. Each output line can’t be wider than 40 symbols (including the hyphen ‘-‘ and excluding the line feed). If there are several rules that can be used the the word is to be carried to the next line according to the rule that provides the minimal length of the carried part of the word. If a word can’t be carried to the next line so that the length of the line wouldn’t exceed 40 the word should be carried to the next line wholly. The hyphenation rules are not case sensitive (the rule “m-Ing” can be used in the word “SwImMiNg”). The existing line feeds, spaces and stops must be saved.

Sample

input
12
un-usual
for-ced
re-al
sum-mer
N-ED
home-work
sec-ret
ho-lidays
Wi-zard
th-Er
L-so
Holi-days
Harry Potter was a highly unusual boy in many ways. 
For one thing, he hated the summer holidays more than any 
other time of year. For another, he really 
 wanted to do his homework but was forced to do it in 
secret, in the dead of night. And he also happened 
to be a wizard.
output
Harry Potter was a highly unusual boy in
 many ways. 
For one thing, he hated the summer holi-
days more than any 
other time of year. For another, he 
really 
 wanted to do his homework but was for-
ced to do it in 
secret, in the dead of night. And he al-
so happened 
to be a wizard.
Problem Author: Den Raskovalov
Problem Source: Open collegiate programming contest for high school children of the Sverdlovsk region, October 11, 2003