Unique suffixes

You start with an empty string (s). You will then 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 to (s).

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

Your task is to output "(+)" for each second-type query if the specified 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 following (q) lines contain queries in the format described above. It is guaranteed that all queries are valid. The first query will always be of the first type. The character (c) in each first-type query will be one of the characters "(a)", "(b)", "(c)", "(d)", "(e)". The number (l) in all second-type queries will be positive and will not exceed the current length of the string (s).

Output

Output (q) lines — the results of the second-type queries. Print the results in the order they appear in the input.

Examples