Unique Suffixes (online version)#5944
You have an initially empty string . You will receive queries, which can be of two types:
A query to append a character to the end of the string . This query is formatted as "", where is the character to be added.
A query to check if the suffix of the string is unique. This query is formatted as "", where is the length of the suffix to be checked. A suffix is unique if it appears exactly once in 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.
The first line contains a single integer (1 \leq q \leq 2 \cdot 10^6) — the number of queries.
The next 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 in each query of the first type is one of "", "", "", "", "". The number in each query of the second type is positive and does not exceed the current length of .
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 "", you add ""; instead of "", you add ""; instead of "", you add ""; instead of "", you add ""; and instead of "", you add "". The first query remains unchanged, as does the addition in case of non-uniqueness of the previous suffix.
Output the results of the second type of queries in the order they appear in the input.
Example 1