You are given a dictionary of words and a target string s. Decide whether s can be written as a concatenation of one or more dictionary words. Each dictionary word may be used any number of times (including not at all), and the words must join together with nothing between them to spell exactly s.
Input format
Line 1: an integer k, the number of dictionary words.
Line 2: k space-separated dictionary words.
Line 3: the target string s.
All words and s consist only of lowercase letters a-z.
Output format
Print YES if s can be segmented into dictionary words, otherwise print NO.
Constraints
- 1 <= k <= 100
- 1 <= length of each dictionary word <= 20
- 1 <= length of
s<= 1000