Word Break Problem

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

Formally, given a string s and a set of words W, determine if there exists a sequence of indices:

$$0 = i_0 < i_1 < \cdots < i_k = |s|$$

such that for every j from 0 to k-1, the substring \(s[i_j:i_{j+1}]\) is in W. For example, if s = "leetcode" and W = {"leet", "code"}, then the answer is True since "leet" and "code" form the string.

This is a classic dynamic programming problem where you can use a boolean DP array to decide whether the substring up to a given index can be segmented.

inputFormat

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

1. The first line contains the string s.
2. The second line contains an integer n denoting the number of words in the dictionary.
3. The third line contains n space-separated words representing the dictionary.

outputFormat

Output a single line to standard output (stdout) with either True or False (without quotes), indicating whether the string can be segmented into one or more dictionary words.

## sample

leetcode
2
leet code

True

</p>