Giải mã thông điệp


Submit solution

Points: 4
Time limit: 1.0s
Memory limit: 98M

Author:
Problem types

Sau khi tốt nghiệp đại học ngành CNTT, Toto làm liên lạc viên cho một trạm thu nhận xử lý tín hiệu vệ tinh chuyên đón nhận các thông tin từ ngoài vũ trụ gửi vào trái đất. Sau một thời gian làm việc Toto đã tìm ra quy luật để dự đoán giải mã những thông điệp này và lập một từ điển để tra cứu những từ đã tìm ra quy luật giả mã. Với một thông điệp đầu vào Toto cắt thành các từ con và tra vào từ điển của mình để ra ngữ nghĩa của thông điệp. Nhưng vì nghiên cứu chưa lâu lên những thông điệp đầu vào này Toto giải nghĩa có thể ra nhiều cách khác nhau.

Ví dụ

Với từ điển mỗi từ chỉ có duy nhất một nghĩa đã có như sau

homang  daita
bo      di
vao     tham
rung    chientruong
ho      daiuy
mang    vacsung
bova    ve   
orung   nha
xanu    choi

Thì thông điệp "homangbovaorung" có các cách hiểu như sau

daita di tham chien truong
daita ve nha
daiuy vacsung di tham chien chuong
daiuy vacsung ve nha

Input

Dòng đầu là thông điệp cần giải mã là một xâu có độ dài không vượt quá \(200\) ký tự

Dòng tiếp theo chứa số lượng từ trong từ điển \(n (1 \le n \e 100)\)

Cuối cùng gồm \(n\) dòng, mỗi dòng gồm thông tin và giải mã đều chỉ chứa ký tự thường tiếng Anh không chứa khoảng trống và độ dài mỗi lại không vượt quá 10 ký tự

Output

Hãy in ra các cách giải mã là các xâu có thêm các khoảng trống để ngăn cách các từ tạo thành danh sách tăng dần theo từ điển. Nếu không giải được mã in ra "Toto bo tay"

Ví dụ 1

Input

homangbovaorung
9
homang  daita
bo      di
vao     tham
rung    chientruong
ho      daiuy
mang    vacsung
bova    ve   
orung   nha
xanu    ngu

Output

daita di tham chientruong
daita ve nha
daiuy vacsung di tham chientruong
daiuy vacsung ve nha

Ví dụ 2

Input

homnaynghihocmonthuattoan
8
homang  daita
bo      di
vao     tham
rung    chientruong
ho      daiuy
mang    vacsung
bova    ve   
orung   nha

Output

Toto bo tay
tichpx

Comments

There are no comments at the moment.