Prefix Tree Membership Op Log

A search box maintains a growing collection of words. You must process q operations in order. Each operation is one of:

• ADD w - insert the word w into the collection (the same word may be added more than once; that has no extra effect).
• EXACT w - answer whether w has been added as a complete word so far.
• PREFIX p - answer whether at least one added word has p as a prefix (a word is a prefix of itself).

Every word and prefix consists of lowercase English letters only.

Input format

Line 1: an integer q, the number of operations. Each of the next q lines: one operation, either ADD w, EXACT w, or PREFIX p.

Output format

For each EXACT and PREFIX operation, in order, print a line containing YES or NO.

Constraints

• 1 <= q <= 100000
• Each word/prefix has length 1..15, lowercase English letters.