Akash is one of the finest programmers of AUST. His closest senior Shuvro asked him if he can solve a real life problem.
The problem is based on our daily life usage of contact searching in any smartphone.
Shuvro described the problem as follows:
You need to design a system which supports two types of queries. For both types of queries you are given a word as an input.
For type 1: Insert the given word in the word storage.
For type 2: You need to search a word from the word storage whose prefix matches exactly with the given input word. If there are several words in the word storage whose prefix matches exactly with the given input word, then you need to output the lexicographically smallest one.
For example, If the word storage contains "ant", "ab", "anticipate" and you perform a query(type 2) for the word "an". You should get "ant" as the output.
It is possible that no such word exists whose prefix matches with the given input word.
A period(.) can be given as an input word for type 2 query. Period (.) denotes an empty string in this problem.
When you get a period(.) (no lowercase characters, only a period(.)) as an input word , you should print the lexicographically smallest word in the word storage.
Note that, the given input word itself can exist as a word in the word storage.
The first line consists of one integer Q (1 <= Q <= 10^5), denoting the number of queries.
Following Q lines contain T (1 <= T <= 2) and S (only lowercase characters or . (period)) denoting the type and the word respectively.
1 <= length(S) <= 10^5
It is guaranteed that, (Q x sum of all length(word)) does not exceed 10^6.
For each type 2 query, output the lexicographically smallest word whose prefix matches with the given input word.
If no such word exists in the word storage, then print "No word found!"(without quotes).
6 1 anticipated 2 ant 1 anti 2 ant 1 ant 2 .
anticipated anti ant
10 1 anticipated 2 ant 1 anti 2 ant 1 ant 2 an 2 a 2 ab 2 an 2 antic
anticipated anti ant ant No word found! ant anticipated