Word Breaker

You are given a string (S) and a dictionary of valid words. Your task is to determine whether (S) can be segmented into a sequence of one or more dictionary words. In other words, you need to decide if there exists a way to insert spaces into (S) such that every resulting segment is a word in the dictionary. One popular approach is to use dynamic programming with the following recurrence:

[ dp[i] = \begin{cases} \text{true} & \text{if } \exists, 0 \leq j < i \text{ such that } dp[j] \text{ is true and } S[j:i] \text{ is in the dictionary} \ \text{false} & \text{otherwise} \end{cases} ]

where (dp[i]) indicates whether the substring (S[0:i]) can be segmented into dictionary words. This method runs in polynomial time and is effective for moderate input sizes.

inputFormat

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

• The first line contains a single integer (n), representing the number of words in the dictionary.
• The second line contains (n) words separated by spaces.
• The third line contains the string (S) that you need to segment.

outputFormat

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

2
apple pen
applepenapple

True