Gifted Composer

Acesrc is a gifted composer. He likes writing tuneful and melodic songs. Every song he writes can be viewed as a sequence of musical notes, and each musical note represents the pitch and the duration of the sound. In this problem, we consider only the following seven primary pitches

do re mi fa sol la si

and the duration of each note is one unit time. Hence, there are only seven types of notes, and we may use the pitch name to represent a note.

Acesrc composes a song in the following way. Initially, the sequence of notes is empty. Every day, he inserts a new note at the beginning or at the end of the sequence, until the song is done.

Acesrc particularly likes songs with repetitions. For a song with $n$ musical notes, we say the song has a repetition of length $k$ $(1 \leq k \leq n)$, if the song can be partitioned into one or more identical sections with $k$ notes, optionally followed by an incomplete section, which is an initial part of a complete section. For example, do re do re do can be partitioned into do re | do re | do, so it has a repetition of length 2; similarly, do re mi do re mi has a repetition of length 3, and do re do re mi has a repetition of length 5.

Acesrc wants to know, after he adds a note each day, the number of different lengths of repetitions the song has. Can you help him?

The first line contains a single integer $n$ $(1 \leq n \leq 10^6)$, the number of days Acesrc uses to compose the song. Each of the remaining $n$ lines contains a character $c$ $(c \in \{$p, a$\})$ and a string $s$ $(s \in \{$do, re, mi, fa, sol, la, si$\})$. On the $i$th day, p means Acesrc prepends $s$ to the sequence, and a means he appends $s$ to the end.

Output $n$ lines. The $i$th line contains a single integer, the answer for the $i$th day.