DNA Decoding

Scientists are excavating fossilized remains of ancient creatures on a planet in a neighboring star system. They want to understand how the DNA strands of these creatures were assembled from genes.

Each DNA strand is a sequence of nucleotides. Each nucleotide is written as a lowercase Latin letter, so a DNA strand is a string of lowercase Latin letters.

A gene is also a string of lowercase Latin letters. In any valid set of genes, no gene is a prefix of another gene.

A DNA strand $d$ can be decoded with a gene set $G$ if $d$ can be written as the concatenation of one or more genes, $d = g_1g_2\ldots g_k$, where each $g_i$ is a gene from $G$. The same gene may appear in the decoding several times.

The team needs a computer system that maintains a valid gene set $G$ and an array $D$ of DNA strands. As the remains are analyzed, the scientists add a new gene to $G$ or append a new DNA strand to $D$. It is guaranteed that no gene in $G$ is a prefix of another gene at any moment.

After each operation, the scientists want to know which strands in $D$ can now be decoded with the current set $G$. After the $i$-th operation, the system must report $k_i$, the number of strands in $D$ that became decodable for the first time after that operation, followed by the $k_i$ indices of those strands. Strands are numbered from 1 in the order they were appended to $D$. The answer to each operation must be printed before the next operation is revealed.

The first line contains the number of operations $n$ ($1 \le n \le 100\,000$).

Each of the next $n$ lines starts with + if the operation adds a gene to $G$, or with ? if it appends a DNA strand to the end of $D$. A space follows, then a string $x_i$ of lowercase Latin letters. The string $s_i$ that is actually added is derived from $x_i$ as follows.

If $i = 1$, then $s_i = x_i$. Otherwise, let $k_{i-1}$ be the number of strands that became decodable for the first time after the previous operation. Move the first character of $x_i$ to the end, $k_{i-1}$ times. In other words, $s_i$ is $x_i$ cyclically shifted left by $k_{i-1}$.

All strings are non-empty, and the total length of the strings over all operations does not exceed $10^6$. It is guaranteed that no gene in $G$ is a prefix of another gene at any moment.

Print $n$ lines. On line $i$, print $k_i$, followed by the $k_i$ numbers of the strands in $D$ that became decodable for the first time after the $i$-th operation. The numbers may be printed in any order.

The first three strings $s_1$, $s_2$, $s_3$ match the input strings. Since $k_3 = 1$, the string $s_4$ for the fourth operation is dabdab shifted left by 1, which gives abdabd. So the fourth operation appends abdabd to $D$. Finally, $k_4 = 0$, so $s_5 = x_5$.