Unique Suffixes (online version)

You have an initially empty string (s). You will receive (q) queries, which can be of two types:

1. A query to append a character to the end of the string (s). This query is formatted as "(+ c)", where (c) is the character to be added.

2. A query to check if the suffix of the string (s) is unique. This query is formatted as "(? l)", where (l) is the length of the suffix to be checked. A suffix is unique if it appears exactly once in (s) as a substring, starting from position (|s|-l+1) (considering the string's characters as one-indexed).

Your task is to output "(+)" for each query of the second type if the suffix is unique, or "(-)" if it is not.

Input

The first line contains a single integer (q) ((1 $\le$ q $\le$ 2 $\times$ 10^6)) — the number of queries.

The next (q) lines contain the queries as described. All queries are guaranteed to be valid. The first query is guaranteed to be of the first type. The character (c) in each query of the first type is one of "(a)", "(b)", "(c)", "(d)", "(e)". The number (l) in each query of the second type is positive and does not exceed the current length of (s).

To add complexity, an artificial method makes this an online problem. This method involves the following: each time a character is added, if the previous suffix check query returned positive (i.e., the suffix was unique), the character to be added is shifted forward cyclically by one. For example, if the previous suffix was unique, instead of adding "(a)", you add "(b)"; instead of "(b)", you add "(c)"; instead of "(d)", you add "(e)"; and instead of "(e)", you add "(a)". The first query remains unchanged, as does the addition in case of non-uniqueness of the previous suffix.

Output

Output the results of the second type of queries in the order they appear in the input.

Examples