Unique suffixes#4658
You start with an initially empty string . Then, you will receive queries. Each query is of one of two types:
1. A query to append a character to the end of the string . This query has the form , where is the character to append to . 2. A query to check whether a suffix of is unique. This query has the form , where is the length of a suffix of to check for uniqueness. A suffix is considered unique if it appears as a substring in exactly once: starting from position |s| - l + 1 (if symbols are counted from ).
Your task is: after each second-type query, output "+" if the given suffix is unique, or "-" in the opposite case.
The first line contains a single integer (1 \leq q \leq 2 \times 10^6) — the number of queries.
The next lines each contain a query in the format described above. It is guaranteed that all queries are correct. The first query is always of the first type. It is guaranteed that the character in every first-type query is one of the characters "a", "b", "c", "d", or "e". It is guaranteed that the number in any second-type query is positive and does not exceed the current length of .
For each second-type query, print a line with the answer. Output the answers in the order the queries appear in the input.
Example 1