Score Betting

Amel and Nina bet on scores using strings made of lowercase English letters and digits $\mathbf{0}$-$\mathbf{9}$. Amel builds a string that earns the highest possible score, and Nina builds a string that earns the lowest possible score. Each string they build must have length at least 1.

The score of a string $A$ is the sum of two parts added together:

• the total score of the strings in the prefix list that are prefixes of $A$
• the total score of the strings in the suffix list that are suffixes of $A$

If no string in a list satisfies the condition, that list contributes $0$. Both lists start empty.

The prefix list and the suffix list keep changing during the bet, so Amel and Nina have trouble deciding at each moment which string would be most favorable to build.

Help Amel and Nina process the following queries.

• < str X: Adds the string str with score $X$ to the prefix list. If str is already in the list, its score is changed to $X$.
• > str X: Adds the string str with score $X$ to the suffix list. If str is already in the list, its score is changed to $X$.
• +: Prints the maximum score Amel can earn.
• -: Prints the minimum score Nina can earn.

The first line contains the number of queries $Q$ ($1\le Q \le 300\,000$).

Each of the next $Q$ lines contains one query.

• $-10^9 \le X \le 10^9$, and $X$ is an integer.
• Every string in the input has length at least 1 and consists only of lowercase English letters. Digits $\mathbf{0}$ to $\mathbf{9}$ do not appear in the input strings.
• The total length of all strings in the input does not exceed $1\,000\,000$.
• There is at least one + or - query.

For each + and - query, print the result on its own line.

In the sample output, the strings that earn each score are, in order, abc, 111, abcd, ab123, and abc.