Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Yet another Real Life Problem

By error26 · Limits 1s, 512 MB

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.

Input

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.

Output

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).

Samples

InputOutput
6
1 anticipated
2 ant
1 anti 
2 ant 
1 ant 
2 .
anticipated
anti
ant
InputOutput
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

    Discussion

    Statistics


    64% Solution Ratio

    Sourav1234Earliest, 1M ago

    EdgedancerFastest, 0.1s

    YouKnowWhoLightest, 55 MB

    YouKnowWhoShortest, 978B

    Submit

    Login to submit