题目描述

科学家正在研究古生物 DNA 链如何由基因拼接而成。

DNA 链是由小写英文字母组成的字符串。一个基因也是由小写英文字母组成的字符串。任意时刻，基因集合 $G$ 都满足：不存在两个基因，使得其中一个是另一个的前缀。

称 DNA 链 $d$ 可以用基因集合 $G$ 解码，如果 $d$ 可以表示为一个或多个基因的顺次拼接：

其中每个 $g_i$ 都属于 $G$，同一个基因可以使用多次。

系统需要动态维护基因集合 $G$ 和 DNA 链数组 $D$。每次操作可能是：

• 添加一个新基因到 $G$；
• 添加一条新 DNA 链到数组 $D$ 的末尾。

保证任意时刻 $G$ 都保持前缀无关性质。

每次操作之后，需要输出本次操作后 第一次变得可解码 的 DNA 链数量，以及这些 DNA 链的编号。DNA 链按加入 $D$ 的顺序从 1 编号。必须在线输出，即下一次操作到来前输出本次答案。

为了防止离线处理，输入中的字符串需要根据上一轮输出的 $k_{i-1}$ 做循环移位。

输入格式

第一行包含整数 $n$，表示操作数。

接下来 $n$ 行，每行描述一次操作：

• 行首为 + 表示添加基因；
• 行首为 ? 表示添加 DNA 链；
• 后面跟一个字符串 $x_i$。

真正加入的字符串 $s_i$ 由 $x_i$ 得到：

• 若 $i=1$，则 $s_i=x_i$；
• 否则设上一次操作后首次可解码的 DNA 链数量为 $k_{i-1}$，将 $x_i$ 循环左移 $k_{i-1}$ 次，得到 $s_i$。

约束：

• $1\le n\le 100000$；
• 所有字符串非空；
• 所有操作中的字符串总长度不超过 $10^6$；
• 任意时刻基因集合中不存在前缀关系。

输出格式

输出 $n$ 行。

第 $i$ 行先输出 $k_i$，即第 $i$ 次操作后首次变得可解码的 DNA 链数量；随后输出 $k_i$ 个整数，表示这些 DNA 链的编号。编号顺序任意。

样例输入

5
? abcabd
+ abc
? abcabc
? dabdab
+ abd

样例输出

0
0
1 2
0
2 1 3

样例说明

前三次操作中，$s_1,s_2,s_3$ 与输入中的字符串相同。由于 $k_3=1$，第四次操作中字符串 dabdab 左移 1 位，得到 abdabd。第五次操作前 $k_4=0$，所以 $s_5=x_5$。