Implement Trie

Implement a Trie (prefix tree) that supports inserting a word, searching for a complete word, and checking whether any inserted word starts with a given prefix.

Input Format

The first line contains an integer Q. Each of the next Q lines is one of: insert W — insert the word W search W — is W a previously inserted word? startsWith P — is P a prefix of any inserted word?

Output Format

For each search and each startsWith, print 1 for yes or 0 for no, one per line.