String Segmentation

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

You are required to use dynamic programming to solve the problem. One way to formulate the DP relation is:

$$dp[i] = \bigvee_{0 \leq j < i} \Big( dp[j] \wedge \big( s[j:i] \in D \big) \Big), \quad dp[0] = true, $$

where D is the dictionary. The output should be True if the string can be segmented into valid words from the dictionary, and False otherwise.

The input is provided via standard input and the result must be printed to standard output.

inputFormat

The input is read from stdin and has the following format:

1. A non-empty string s.
2. An integer n representing the number of words in the dictionary.
3. n lines each containing a word.

Example:

applepenapple
5
apple
pen
applepen
pine
pineapple

outputFormat

Output a single line to stdout with either True or False depending on whether the given string can be segmented into one or more words from the dictionary.

## sample

applepenapple
5
apple
pen
applepen
pine
pineapple

True