A keyword watcher is given a set of n keywords, then reads a stream of characters one at a time. After each character arrives, report Y if some keyword equals a suffix of the characters read so far, and N otherwise.
The standard trie approach stores the keywords reversed, so that after each new character you can walk backward through the recent characters. Keywords and the stream consist of lowercase English letters only.
Input format
Line 1: an integer n.
Line 2: n space-separated keywords.
Line 3: the stream, a non-empty string of lowercase letters.
Output format
A single line: a string of Y/N, one character per stream position, in order.
Constraints
- 1 <= n <= 2000
- Each keyword has length 1..200, lowercase letters.
- The stream has length 1..40000, lowercase letters.