Унікальні суфікси (online версія)
У вас є початково порожній рядок s. Вам потрібно обробити q запитів, які можуть бути двох типів:
Запит на додавання символу в кінець рядка s. Формат запиту: "+ c", де c — символ, який слід додати в кінець рядка s.
Запит на перевірку унікальності суфікса рядка s. Формат запиту: "? l", де l — довжина суфікса поточного рядка s, який потрібно перевірити на унікальність. Суфікс вважається унікальним, якщо він зустрічається в рядку s як підрядок рівно один раз (починаючи з позиції |s|-l+1, якщо рахувати символи рядка з одиниці).
Ваше завдання — після кожного запиту другого типу вивести "+", якщо заданий суфікс унікальний, або "-", якщо ні.
Вхідні дані
У першому рядку записано єдине ціле число q (1 ≤ q ≤ 2·10^6) — кількість запитів.
У наступних q рядках записані запити у форматі, описаному в умові. Гарантується, що всі запити коректні. Перший запит завжди буде першого типу. Символ c у кожному запиті першого типу є одним із символів "a", "b", "c", "d", "e". Число l у всіх запитах другого типу є позитивним і не перевищує поточної довжини рядка s.
Щоб ускладнити задачу, використовується штучний метод для перетворення задачі в online типу. Метод полягає в наступному: кожного разу, коли надходить запит на додавання символу, якщо відповідь на попередній запит на перевірку унікальності суфікса була позитивною (тобто, суфікс виявився унікальним), тоді поточний додаваний символ циклічно зсувається на один вперед. Іншими словами, якщо попередній суфікс був унікальним, замість символу "a" додається "b"; замість "b" — "c"; замість "c" — "d"; замість "d" — "e"; замість "e" — "a". Перший запит не змінюється, як і запит на додавання у випадку не унікальності попереднього суфікса.
Вихідні дані
Виведіть відповіді на запити другого типу в порядку їх появи у вхідних даних.