String Segmentation

Given a non-empty string s and a dictionary of words, determine whether s can be segmented into a space-separated sequence of one or more dictionary words.

You are provided with the string and the set of valid words. A valid segmentation means that the entire string s is composed of one or more words that all exist in the dictionary. If s is empty, then it is considered not segmentable.

Note: All dictionary words and the string s consist of lowercase English letters.

The problem can be formulated using the following recurrence relation:

\(dp[i] = \bigvee_{0 \le j < i} (dp[j] \wedge (s[j:i] \in D))\), where \(D\) is the dictionary. The answer will be \(dp[n]\) if \(n\) is the length of the string.

inputFormat

The first line contains a string s.

The second line contains an integer n, denoting the number of words in the dictionary.

The following n lines each contain a word, representing the dictionary.

outputFormat

Output a single line containing either True or False depending on whether the string s can be segmented into a sequence of dictionary words.

## sample

3
apple
pie
pear

False