Word Segmentation

You are given a list of dictionary words and a target string. Your task is to determine whether the target string can be segmented into a sequence of one or more dictionary words. More formally, define a boolean array \(dp\) of length \(n+1\) (where \(n\) is the length of the string) with the recurrence:

$$dp[i] = \bigvee_{j=0}^{i-1} \Bigl(dp[j] \wedge \bigl( s[j:i]\ \text{is in the dictionary} \bigr)\Bigr)$$

The answer is \(dp[n]\). Note that an empty string is considered to be segmentable.

Input: The first line contains an integer \(n\) representing the number of dictionary words. The second line contains \(n\) space-separated words. The third line contains the target string \(s\).

Output: A single line with either True or False indicating whether the string can be segmented.

inputFormat

The input consists of three lines:

• The first line contains an integer \(n\), the number of words in the dictionary.
• The second line contains \(n\) space-separated words.
• The third line contains the string \(s\) to be segmented.

outputFormat

Output a single line: True if the string can be segmented into one or more words from the dictionary, otherwise False.

## sample

2
apple pen
applepenapple

True

</p>