Word Segmentation Problem

Given a string (s) and a list of words (dictionary), determine if (s) can be segmented into a space-separated sequence of one or more dictionary words. Formally, you are to decide whether there exists a sequence of indices (0 = i_0 < i_1 < \dots < i_k = |s|) such that every substring (s[i_{j-1}:i_j]) (for (1 \le j \le k)) is contained in the dictionary. This problem can be solved efficiently using dynamic programming.

inputFormat

The input is given from standard input (stdin). The first line contains the string (s). The second line contains an integer (n), the number of words in the dictionary. Each of the following (n) lines contains one word from the dictionary.

outputFormat

Output to standard output (stdout) a single line with either (True) if the string can be segmented into dictionary words, or (False) otherwise.## sample

applepenapple
2
apple
pen

True