Word Break Problem

You are given a dictionary of words and a target string s. Your task is to determine whether the target string can be segmented into a space‐separated sequence of one or more dictionary words.

Formally, let the dictionary be a set \(D\) and \(s\) be a string. You need to decide if there exists a sequence of indices \(0 = i_0 < i_1 < \cdots < i_k = |s|\) such that for every \(j\) with \(0 \le j < k\), the substring \(s[i_j:i_{j+1}]\) is in \(D\). In terms of dynamic programming, the recurrence is given by:

[ \text{dp}[i] = \bigvee_{0 \le j < i} \left(\text{dp}[j] \land \mathbf{1}_{{s[j:i] \in D}}\right)\quad,\quad \text{dp}[0]=1, ]

For example:

• If D = {"apple", "pen"} and s = "applepenapple", then the output is True.
• If D = {"cats", "dog", "sand", "and", "cat"} and s = "catsandog", the output must be False since "catsandog" cannot be segmented properly.

An empty string is considered to be segmentable.

inputFormat

The input is read from stdin and is formatted as follows:

1. An integer n representing the number of words in the dictionary.
2. A line containing n words separated by spaces.
3. A line containing the target string s. Note that s can be an empty string.

outputFormat

Output to stdout a single line: True if the string can be segmented into a sequence of dictionary words, or False otherwise.

## sample

2
apple pen
applepenapple

True