재능 있는 작곡가

시간 제한4초메모리 제한256 MB

요약

매일 음표를 앞이나 뒤에 붙인 뒤, 곡을 길이 k인 블록들의 반복으로 나눌 수 있는 k의 개수를 셉니다. 마지막 블록은 일부만 있어도 됩니다.

난이도: 어려움10점 중 8점
유형: 문자열 매칭, 문자열
정답자: 아직 제출이 없습니다

문제

Acesrc는 재능 있는 작곡가다. 그는 선율이 아름답고 멜로디가 살아 있는 노래를 만들기를 좋아한다. 그가 쓴 노래는 모두 음표의 나열로 볼 수 있으며, 각 음표는 소리의 음높이와 길이를 나타낸다. 이 문제에서는 다음 일곱 가지 기본 음높이만 고려한다.

do re mi fa sol la si

각 음표의 길이는 한 단위 시간이다. 따라서 음표는 일곱 종류뿐이며, 음높이 이름으로 음표 하나를 나타낼 수 있다.

Acesrc는 다음 방식으로 노래를 만든다. 처음에는 음표의 나열이 비어 있다. 노래가 완성될 때까지 매일 그는 나열의 맨 앞이나 맨 뒤에 새 음표를 하나 넣는다.

Acesrc는 반복이 있는 노래를 특히 좋아한다. 음표가 $n$ 개인 노래에 대해, 노래를 길이 $k$ 인 동일한 구간 하나 이상으로 나눌 수 있고, 그 뒤에 완전한 구간의 앞부분인 불완전한 구간이 선택적으로 붙을 수 있으면, 이 노래는 길이 $k$ 의 반복을 가진다고 한다 ( $1 \leq k \leq n$ ). 예를 들어 do re do re do는 do re | do re | do로 나눌 수 있으므로 길이 2의 반복을 가진다. 마찬가지로 do re mi do re mi는 길이 3의 반복을 가지며, do re do re mi는 길이 5의 반복을 가진다.

Acesrc는 매일 음표를 하나씩 추가한 뒤, 노래가 가진 서로 다른 반복 길이의 개수를 알고 싶어 한다. 그를 도와줄 수 있는가?

입력

첫 줄에 Acesrc가 노래를 만드는 데 쓰는 날의 수 $n$ $(1 \leq n \leq 10^6)$ 이 주어진다. 이어지는 $n$ 개의 줄에는 문자 $c$ $(c \in \{$ p, a $\})$ 와 문자열 $s$ $(s \in \{$ do, re, mi, fa, sol, la, si $\})$ 가 주어진다. $i$ 일째에 p는 $s$ 를 나열의 맨 앞에 넣는다는 뜻이고, a는 $s$ 를 맨 뒤에 넣는다는 뜻이다.

출력

$n$ 개의 줄을 출력한다. $i$ 번째 줄에는 $i$ 일째의 답을 한 정수로 쓴다.

예제2

예제 1
입력
```
5
a do
p re
a re
a do
p do
```
예상 출력
```
1
1
2
2
3
```
예제 2
입력
```
5
a re
a do
a re
p do
a mi
```
예상 출력
```
1
1
2
2
1
```