Design a data structure that supports adding new words and finding if a string matches any previously added string.

• addWord(word) — adds word to the data structure.
• search(word) — returns true if there is any string in the data structure that matches word. word may contain dots . where dots can be matched with any letter.

Example:

Input:
addWord bad
addWord dad
addWord mad
search pad
search bad
search .ad
search b..

Output:
false
true
true
true

Constraints:

• 1 ≤ word.length ≤ 25
• word in addWord consists of lowercase English letters.
• word in search consists of . or lowercase English letters.
• At most 10⁴ calls to addWord and 10⁴ calls to search.

Input format: One command per line.

Output format: Print a line only for search.