Унікальні суфікси
У Вас є спочатку порожній рядок 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.
Вихідні дані
Виведіть q рядків — відповіді на запити другого типу. Відповіді на запити виводьте у порядку появи запитів у вхідних даних.