{"problem":{"name":"C. Call from Mendes","description":{"content":"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10244C"},"statements":[{"statement_type":"Markdown","content":"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\".\n\nTired 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.\n\nThey 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.\n\nTo check if their discoveries are correct, you were assigned to write a program that answers 3 types of queries: \n\n_Where the index of the word is the index of the query it was inserted in the dictionary (1-indexed)_\n\nYou will receive an integer $Q$ ($1 < Q <= 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.\n\nThe 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.\n\nSum of lengths of strings in queries 1 and 3 will not exceed $10^6$. Furthermore, all strings will consist only of lowercase Latin letters.\n\n## Input\n\nYou will receive an integer $Q$ ($1 < Q <= 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.\n\n## Output\n\nThe 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.\n\n[samples]\n\n## Note\n\nSum of lengths of strings in queries 1 and 3 will not exceed $10^6$. Furthermore, all strings will consist only of lowercase Latin letters.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ Q \\in \\mathbb{Z} $ be the number of queries.  \nLet $ D \\subseteq \\mathbb{Z}^+ \\times \\Sigma^* $ be a dynamic dictionary, where each element $ (i, w) $ represents a word $ w \\in \\Sigma^* $ inserted at query index $ i $ (1-indexed).  \nLet $ \\Sigma = \\{a, b, \\dots, z\\} $ be the set of lowercase Latin letters.\n\n**Constraints**  \n1. $ 1 < Q \\leq 10^5 $  \n2. For each query:  \n   - Type 1: Insert word $ w \\in \\Sigma^* $ into $ D $ with index $ i $ (current query index).  \n   - Type 2: Remove word $ w \\in \\Sigma^* $ from $ D $ (guaranteed to exist).  \n   - Type 3: Given prefix $ p \\in \\Sigma^* $, find $ \\arg\\min_{(i, w) \\in D,\\, p \\preceq w} i $, where $ p \\preceq w $ means $ p $ is a prefix of $ w $. If no such word exists, return $-1$.  \n3. All words in $ D $ are distinct at all times.  \n4. Sum of lengths of strings in Type 1 and Type 3 queries $ \\leq 10^6 $.\n\n**Objective**  \nFor each Type 3 query with prefix $ p $, output:  \n$$\n\\begin{cases}\n\\min\\{ i \\mid (i, w) \\in D \\text{ and } p \\preceq w \\} & \\text{if } \\exists (i, w) \\in D \\text{ s.t. } p \\preceq w \\\\\n-1 & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10244C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}