O-recnik
Little Deka decided to make his own dictionary. He put inside all the words he has found. Naturally, as in any dictionary, words are sorted in lexicographic order from the smallest to the largest. From time to time, Deka wants to know how many words smaller than a given word there exist.
InputIn the first line you are given an integer, N (1 <= N <= 100000) representing the number of the incoming commands.
Each of the next N lines contains one of the two following commands
ADD word
LESS word
Each word is a string consisted of English lowercase and uppercase letters, but in the dictionary we assume that words "PoPoKaTaPeTL" and "POPOkataPETl" are the same.Words will be no longer than 100 letters and whole dictionary will have less then 2 000 000 letters.
Each of the next N lines contains one of the two following commands
ADD word
LESS word
Each word is a string consisted of English lowercase and uppercase letters, but in the dictionary we assume that words "PoPoKaTaPeTL" and "POPOkataPETl" are the same.Words will be no longer than 100 letters and whole dictionary will have less then 2 000 000 letters.
OutputFor a command LESS you must print, on the standard output, how many words in the dictionary are lexicographically smaller than the word given by the command. Every answer must be printed on a new line. If there does not exist such a word you must print "no such word" (without quotes).
NOTICE: 50% of Test cases will be N <= 1000.
Input:
14
ADD Petronije
ADD PeTrONIJE
ADD Jovan
ADD STEVAN
LESS Stevan
ADD ISTVAn
LESS pajVan
ADD maja
LESS istvan
ADD KlipaN
ADD Milica
LESS stevan
ADD Milica
ADD MiliCA
Output:
2
no such word
0
6
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.