DNA Decoding
Scientists are conducting excavations of fossilized remains of ancient creatures on a planet in a nearby star system. Their research aims to decipher the composition of DNA strands from various creatures by examining their genetic makeup.
Each DNA strand is a sequence of nucleotides, represented by lowercase Latin letters. Therefore, a DNA strand is essentially a string of these letters.
A gene is also a string of lowercase Latin letters. Importantly, in any valid set of genes, no gene can be a prefix of another.
We say a DNA strand d can be decoded using a set of genes G if d can be expressed as a concatenation of one or more genes: d = g[1]g[2]...g[k], where each g[i] is a gene from the set G. A gene can be used multiple times in decoding a DNA strand.
To facilitate their research, scientists need a computer system that can manage a valid set of genes G and an array of DNA strands D. As they analyze the remains, they may add a new gene to G or a new DNA strand to D. It is guaranteed that no two genes will exist where one is a prefix of the other.
After each operation, scientists want to determine which DNA strands in D can be decoded using the current set of genes G. After the i-th operation, the system should report k[i]—the number of DNA strands in D that can be decoded for the first time after this operation—and then list k[i] indices of these strands. The results of the current operation should be obtained before proceeding to the next.
Help the scientists develop this system.
Input
The first line contains the integer n, the number of operations to be performed (1 ≤ n ≤ 100,000).
The next n lines describe the operations. Each line begins with a "+" if the operation is adding a new gene to G, or a "?" if it is adding a DNA strand to D. Following this symbol is a string x[i] of lowercase Latin letters, which is used to derive the string s[i], defining the gene or DNA strand added in this operation.
To derive s[i] from x[i], follow these steps: If i = 1, then s[i] = x[i]. Otherwise, let k[i-1] be the number of newly decoded DNA strands after the previous operation. Perform a cyclic shift of x[i] to the left by k[i-1] positions to obtain s[i].
All strings are non-empty, and the total length of all strings across operations does not exceed 10^6. It is guaranteed that no two genes will exist where one is a prefix of the other.
Output
Print n lines.
For the i-th line, first print the number k[i]—the count of DNA strands in D that can be decoded for the first time after the i-th operation—followed by k[i] indices of these strands. The strands are numbered starting from one, in the order they are added to D. The indices can be printed in any order.
Note to the example
In the first three operations, s[1], s[2], and s[3] match the input strings directly. Since k[3] = 1, for the fourth operation, s[4] is derived from x[4] = "dabdab" by a left cyclic shift of 1, resulting in s[4] = "abdabd". Finally, k[4] = 0, so s[5] = x[5].