Расшифровка ДНК
Ученые работают на раскопках окаменелых останков древних существ на планете соседней звездной системы. В процессе исследования ученые пытаются понять, как именно цепочки ДНК различных существ составлялись из генов.
Цепочки ДНК всех исследуемых существ представляют собой последовательности нуклеотидов. Каждый нуклеотид обозначется строчной буквой латинского алфавита. Таким образом, цепочка ДНК представляет собой строку, составленную из строчных букв латинского алфавита.
Ген также представляет собой строку из строчных букв латинского алфавита. Известно, что в любом корректном наборе генов никакая строка не является префиксом другой строки.
Будем говорить, что цепочку ДНК 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 6 n 6 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].