DNA 해독

고고학자들이 이웃 항성계의 행성에서 고대 생물의 화석 잔해를 발굴하고 있다. 연구자들은 이 생물들의 DNA 사슬이 유전자로부터 어떻게 조립되었는지 알고 싶어 한다.

DNA 사슬은 뉴클레오티드의 나열이다. 각 뉴클레오티드는 영문 소문자 하나로 표시하므로, DNA 사슬은 영문 소문자로 이루어진 문자열이다.

유전자도 영문 소문자로 이루어진 문자열이다. 올바른 유전자 집합에서는 어떤 유전자도 다른 유전자의 접두사가 되지 않는다.

DNA 사슬 $d$는 유전자 집합 $G$로 해독할 수 있다. $d$를 $G$에 속한 유전자 $g_1, g_2, \ldots, g_k$ ($k \ge 1$)를 순서대로 이어 붙인 결과, 즉 $d = g_1g_2\ldots g_k$로 나타낼 수 있다는 뜻이다. 같은 유전자를 여러 번 써도 된다.

연구팀에는 올바른 유전자 집합 $G$와 DNA 사슬 배열 $D$를 관리하는 컴퓨터 시스템이 필요하다. 유물 분석이 진행되면 연구자는 $G$에 새 유전자를 추가하거나 $D$의 끝에 새 DNA 사슬을 덧붙인다. 어느 시점에도 $G$의 어떤 유전자도 다른 유전자의 접두사가 되지 않는다고 보장된다.

각 연산 후 연구자들은 현재 유전자 집합 $G$로 새롭게 해독할 수 있게 된 DNA 사슬을 알고 싶어 한다. $i$번째 연산 후 시스템은 그 연산 후에 처음으로 해독 가능해진 $D$의 사슬 개수 $k_i$를 보고하고, 이어서 그 사슬들의 번호 $k_i$개를 출력해야 한다. 사슬은 $D$에 추가된 순서대로 1부터 번호를 매긴다. 각 연산의 답은 다음 연산이 주어지기 전에 출력해야 한다.

첫 줄에 연산의 개수 $n$이 주어진다 ($1 \le n \le 100\,000$).

이어지는 $n$개의 줄은 각각 유전자를 추가하는 연산이면 +로, DNA 사슬을 $D$의 끝에 추가하는 연산이면 ?로 시작한다. 공백 뒤에 영문 소문자로 이루어진 문자열 $x_i$가 주어진다. 실제로 추가되는 문자열 $s_i$는 다음과 같이 구한다.

$i = 1$이면 $s_i = x_i$이다. 그 외에는 직전 연산 후 처음으로 해독 가능해진 사슬의 개수를 $k_{i-1}$이라 하자. $x_i$의 첫 글자를 맨 뒤로 옮기는 작업을 $k_{i-1}$번 반복한다. 즉 $s_i$는 $x_i$를 왼쪽으로 $k_{i-1}$만큼 순환 이동한 문자열이다.

모든 문자열은 비어 있지 않으며, 모든 연산의 문자열 길이 합은 $10^6$을 넘지 않는다. 어느 시점에도 $G$의 어떤 유전자도 다른 유전자의 접두사가 되지 않는다고 보장된다.

$n$개의 줄을 출력한다. $i$번째 줄에는 $k_i$를 먼저 출력하고, 이어서 $i$번째 연산 후 처음으로 해독 가능해진 $D$의 사슬 번호 $k_i$개를 출력한다. 번호의 출력 순서는 상관없다.

처음 세 연산의 $s_1$, $s_2$, $s_3$은 입력의 문자열과 같다. $k_3 = 1$이므로 네 번째 연산의 $s_4$는 dabdab를 왼쪽으로 1만큼 순환 이동한 abdabd이다. 따라서 네 번째 연산에서 abdabd가 $D$에 추가된다. 마지막으로 $k_4 = 0$이므로 $s_5 = x_5$이다.