Word Break

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. An empty string is considered to be segmented successfully. For instance, if ( s = \texttt{applepenapple} ) and the dictionary is ( { \texttt{apple}, \texttt{pen} } ), then the answer is True since it can be segmented as "apple pen apple". Your task is to implement an algorithm that uses dynamic programming to decide whether the segmentation is possible.

inputFormat

The input is given from standard input (stdin) in the following format:

Line 1: A string ( s ). Line 2: An integer ( n ) denoting the number of words in the dictionary. The following ( n ) lines: Each line contains one word from the dictionary.

outputFormat

Output a single line to standard output (stdout) that is either "True" or "False" depending on whether the string can be segmented into a sequence of one or more dictionary words.## sample

applepenapple
2
apple
pen

True