F. Engine
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Although Gogu is considered to be the best search engine, we believe you can do something better. Let's do it!

There are 4 types of queries you can make to your custom search engine:

  1. Type a new character in the search bar of the engine. Each time the search engine will suggest the most searched $$$K$$$ words where the current typed word is a prefix. If there are more words with the same frequency, the engine will pick those searched first. If there are less than $$$K$$$ words with this prefix, the search engine will display all of them.
  2. Clear the current search bar of the engine
  3. Delete the last character typed
  4. Press enter and search the current typed word. This word can now be used for future suggestions by the search engine.
Input

The first line of the input contains the integers $$$Q$$$ ($$$1 \leq Q \leq 500.000$$$) and $$$K$$$ ($$$1 \leq K \leq 10$$$), denoting the number of queries and the numbers of words the search engine will try to suggest. The next $$$Q$$$ lines have the following structure:

  • $$$1$$$ $$$C$$$ - to type a letter
  • $$$2$$$ - to clear the current typed word
  • $$$3$$$ - to delete the last typed character
  • $$$4$$$ - to search the current typed word
where $$$C$$$ is a lowercase letter between $$$a$$$ and $$$z$$$.
Output

For each operation of the $$$1^{st}$$$ type print on one line the IDs of the most searched $$$K$$$ words (or less than $$$K$$$ if there are not that many) with the current typed prefix in descending order of their frequency. In case of equality in terms of frequency, the word with the smallest ID goes first. If there is no word with the given prefix print $$$-1$$$. The ID of a word is the index of the first query of type $$$4$$$ which searched it. Please note that the queries are 0-indexed.

Example
Input
19 3
1 a
1 a
4
3
1 a
4
3
1 a
4
3
1 b
4
3
1 c
4
2
1 a
2
1 b
Output
-1
-1
2
2
-1
-1
2 11 14
-1