Mendes, as you might already guess, is also a student from UFPE. He is known for having the worst ideas of all. So much that, when anyone gives a bad idea, it's called a "call from Mendes".
Tired of always falling for Mendes' calls, his friends decided to study how he could know so many different bad ideas. They discovered Mendes has a dictionary of different words in his head, and that everytime he hears his friends say something, he would say the smallest word in length in his dictionary that has the given word as a prefix.
They also discovered that Mendes' dictionary is not static. Sometimes, he gets new ideas from the internet and adds then to his dictionary. He also forgets some words, as they might not be funny anymore.
To check if their discoveries are correct, you were assigned to write a program that answers 3 types of queries:
Where the index of the word is the index of the query it was inserted in the dictionary (1-indexed)
You will receive an integer $$$Q$$$ ($$$1 < Q \le 10^{5}$$$), the number of queries, followed by Q lines of queries in the format specified above. It is guaranteed that every word in his dictionary is different at all times and that every query of type $$$2$$$ is valid.
The output must contain one line for each query of type $$$3$$$. Each line should contain the index of the word Mendes would say to answer that query or $$$-1$$$ if Mendes does not have anything to say.
6 1 call 1 mendes 1 troll 3 mend 2 2 3 mendes
2 -1
Sum of lengths of strings in queries 1 and 3 will not exceed $$$10^{6}$$$. Furthermore, all strings will consist only of lowercase Latin letters.
| UFPE Starters Final Try-Outs 2020 |
|---|
| Закончено |
