Search Engine Query Processor

You are to implement a search engine query processor that supports multiple operations on a collection of documents. Each document is associated with a unique identifier and contains a sequence of words.

The supported operations are:

• A id content: Add a document with the given id and its text content. The content is a space‐separated string of words.
• R id: Remove the document with the given id. If the document does not exist, do nothing.
• S word: Search for all documents that contain the specified word. Return the document ids in the order they were added.
• M id: For the document with the given id, return the word that appears most frequently. In case of a tie, return the lexicographically smallest word. If the document does not exist, return an empty string.

Input is read from standard input (stdin) and the results are printed to standard output (stdout). The first line of input contains an integer Q denoting the number of queries. Each of the following Q lines contains a query in one of the four formats described above. For every query that produces an output (i.e., the S and M commands), output the result on a new line. For a search query, if no document is found, print an empty line.

Note: It is guaranteed that words in the content of documents do not contain whitespace characters.

inputFormat

The input begins with a single integer Q (1 ≤ Q ≤ 10⁵), representing the number of queries. The following Q lines each contain a query. A query is either:

• A d content: Add a document with id d (an integer) and content (a sequence of space separated words).
• R d: Remove the document with id d.
• S word: Search for word in all documents.
• M d: Find the most frequent word in document with id d.

All input is provided via standard input.

outputFormat

For each query that outputs a result (S or M), print the answer on a separate line. For a search query, print the document ids separated by a single space. For the most frequent word query, print the corresponding word or an empty line if the document does not exist.

## sample

3
A 1 hello world
A 2 hello there
S hello

1 2

</p>