DIY: Word Break

Problem statement

You are given a non-empty string s and a list of strings called subs. The subs list will contain a unique set of strings. Your job is to determine if s can be broken down into a space-separated sequence of one or more strings from the subs list. A single string from subs can be reused multiple times in the breakdown of s.

Input

The first input will be a non-empty string called s, and the second input will be a list string called subs. The following is an example input:

magically
["ag", "al", "icl", "mag", "magic", "ly", "lly"]

Output

The output will be a Boolean that represents if the string s can be broken down into substrings from subs. The following is an example output:

true