You are given a lowercase string s and a dictionary of k known "motifs" (each a non-empty lowercase string). Determine whether s can be split into a sequence of one or more consecutive, non-overlapping pieces, EACH of which is exactly one of the dictionary motifs (a motif may be reused any number of times, and the pieces must cover s exactly with no leftover characters).
Input format
Line 1: the string s.
Line 2: an integer k.
Line 3: k space-separated motifs.
Output format
Print YES if s can be fully segmented using the given motifs, otherwise print NO.
Constraints
- 1 ≤ length of s ≤ 200
- 1 ≤ k ≤ 20
- 1 ≤ length of each motif ≤ 10
sand every motif consist only of lowercase English letters