Розшифровка ДНК
Науковці займаються розкопками скам'янілих останків давніх істот на планеті в сусідній зоряній системі. Вони намагаються зрозуміти, як саме ланцюжки ДНК різних істот складалися з генів.
Ланцюжки ДНК всіх досліджуваних істот є послідовностями нуклеотидів, де кожен нуклеотид позначається рядковою літерою латинського алфавіту. Таким чином, ланцюжок ДНК — це рядок, складений з рядкових літер латинського алфавіту.
Ген також є рядком з рядкових літер латинського алфавіту. Відомо, що в будь-якому коректному наборі генів жоден рядок не є префіксом іншого рядка.
Кажемо, що ланцюжок ДНК d можна розшифрувати за допомогою набору генів G, якщо d можна представити як результат послідовного запису одного або кількох генів: d = g[1]g[2]...g[k], де g[i] — гени з набору G. Один і той самий ген може входити в розшифровку ДНК кілька разів.
Для обробки інформації вченим потрібно розробити комп'ютерну систему, яка буде підтримувати коректний набір генів G і масив ланцюжків ДНК істот D. У процесі аналізу останків вчені можуть додавати новий ген у набір G або додавати новий ланцюжок ДНК у масив D. Гарантується, що в жодний момент часу не існує двох генів, один з яких є префіксом іншого.
Після кожної операції вчені хочуть знати, які ланцюжки ДНК у масиві D можна розшифрувати, використовуючи поточний набір генів G. Після i-ї операції система повинна повідомляти k[i] — кількість ланцюжків ДНК, що знаходяться в масиві D, які вперше стало можна розшифрувати після i-ї операції, а потім k[i] чисел — номери цих ланцюжків. Результат чергової операції повинен бути отриманий до того, як стане відома наступна операція.
Допоможіть вченим розробити таку систему.
Вхідні дані
У першому рядку знаходиться число n — кількість операцій, які необхідно виконати (1 ≤ n ≤ 100 000).
У наступних n рядках знаходяться описи операцій, i-й рядок починається з символу «+», якщо ця операція — додавання нового гену в набір G, або з символу «?», якщо ця операція — додавання ланцюжка ДНК в кінець масиву D. Далі через пробіл знаходиться рядок x[i], що складається з рядкових латинських літер, який необхідно використати, щоб отримати рядок s[i], що задає додаваний у цій операції ген або ланцюжок ДНК.
Для отримання рядка s[i] з рядка x[i], необхідно виконати наступні дії. Якщо i = 1, то s[i] = x[i]. Інакше нехай число вперше розшифрованих ланцюжків ДНК після попередньої операції дорівнює k[i-1]. Виконаємо k[i-1] раз наступну дію: перенесемо перший символ x[i] у кінець. Інакше кажучи, виконаємо циклічний зсув рядка x[i] вліво на k[i-1]. Отриманий рядок дорівнює s[i] — ген або ланцюжок ДНК, який необхідно додати на i-й операції.
Усі рядки не порожні, сумарний розмір рядків у всіх операціях не перевищує 10^6. Гарантується, що в жодний момент часу не існує двох генів, один з яких є префіксом іншого.
Вихідні дані
Виведіть n рядків.
У i-му рядку виведіть спочатку число k[i] — кількість ланцюжків ДНК, що знаходяться в масиві D, які вперше стало можна розшифрувати після i-ї операції, а потім k[i] чисел — номери цих ланцюжків. Ланцюжки нумеруються з одиниці в порядку додавання в масив D. Номери ланцюжків в одному рядку можна виводити в будь-якому порядку.
Примітка до прикладу
У перших трьох операціях s[1], s[2] і s[3] збігаються з відповідними рядками у вводі. Оскільки k[3] = 1, то для четвертої операції s[4] отримується з рядка x[4] = «dabdab» циклічним зсувом вліво на 1, таким чином, у четвертій операції в масив D додається рядок s[4] = «abdabd». Нарешті, k[4] = 0, тому s[5] = x[5].