Word Break

Problem statement

A messaging system removes spaces from a sequence of dictionary words. The receiver must determine whether a received string could have been produced this way using only approved dictionary entries. Your task Return true if the entire string can be segmented into one or more dictionary words. A dictionary word may be used multiple times. Important details Every character must belong to exactly one chosen word, with no gaps or rearrangement. A valid prefix alone is not enough. Choosing the longest matching word greedily may fail even when another segmentation succeeds. Worked example For string redred and dictionary [red, blue], use red twice. This covers the entire string, so the answer is true.

Input format

First line: the string. Second line: d. Next d lines: distinct dictionary words.

Output format

Print true if the condition holds, otherwise false.

Constraints

1 <= string length <= 300; 1 <= d <= 1000; 1 <= word length <= 20; lowercase letters.

Sample input

redred
2
red
blue

Sample output

true