Message Segmentation

You are given a message string containing only lowercase alphabetical characters and a dictionary of valid words. Your task is to determine whether the message can be segmented into a space-separated sequence of one or more dictionary words.

For example, consider the message applepie and the dictionary {"apple", "pie"}. The message can be segmented as apple pie, so the answer is True.

This problem can be solved efficiently using a dynamic programming (DP) approach. Let \( dp[i] \) be a boolean value that is true if the substring \( message[0:i] \) can be segmented into dictionary words. The DP recurrence is:

[ dp[i] = \bigvee_{0 \leq j < i} { dp[j] \text{ and } message[j:i] \in \text{dictionary} } ]

The answer is the value of \( dp[n] \) where \( n \) is the length of the message.

inputFormat

The input is given via stdin and has the following format:

message
n
word_1
word_2
... 
word_n

Here:

• message is a string containing only lowercase alphabetical characters.
• n is an integer representing the number of words in the dictionary.
• The next n lines each contain a dictionary word.

outputFormat

Output a single line to stdout containing either True if the message can be segmented into a sequence of one or more dictionary words, or False otherwise.

## sample

applepie
2
apple
pie

True