구역

수도의 대중교통을 개선하려고 교통 회사가 대중교통 구역의 경계를 바꾸기로 했다. 지금까지 쓰던 원형 모델 대신 마름모 모델을 쓴다. 도시는 $1$부터 $N$까지 번호가 붙은 $N$개의 구역으로 나뉜다.

구역 $1$은 도시 한가운데에 중심을 둔, 한 변이 $1$ km인 정사각형이다. 이 정사각형은 45도 기울어져 있어서 네 꼭짓점이 북, 동, 남, 서를 향한다. 구역 $2$는 구역 $1$의 정사각형을 북, 동, 서, 남 중 한 방향으로 넓혀서 한 변이 $2$ km가 되게 만든 것이다. 그다음 구역도 정사각형을 네 방향 중 하나로 넓혀서 얻으며, 넓힐 때마다 한 변이 $1$ km씩 길어진다. 어떤 방향으로 넓히면 새 정사각형은 이전 정사각형을 포함하고, 고른 방향의 반대쪽 꼭짓점을 이전 정사각형과 공유한다. 구역 $i$ ($i \ge 2$)는 $i$번째 정사각형에서 $(i-1)$번째 정사각형을 뺀 영역이다.

아래 그림은 도시를 4개 구역으로 나누는 한 가지 방법이다. 구역 $2$는 북쪽으로, 구역 $3$은 서쪽으로, 구역 $4$는 다시 북쪽으로 넓혔다.

각 구역의 승차권 가격은 그 구역과 경계를 맞대고 있는 구역의 수와 같다. 위 예에서 승차권 가격은 구역 $1$이 2쿠나, 구역 $2$가 3쿠나, 구역 $3$이 3쿠나, 구역 $4$가 2쿠나이다.

각 구역의 승차권 가격을 구하시오.

첫째 줄에 구역의 수 $N$이 주어진다. ($2 \le N \le 300\,000$)

다음 $N-1$개의 줄에는 각각 S, I, Z, J 중 한 글자가 주어진다. 입력의 $i$번째 줄($2 \le i \le N$)에 있는 글자는 구역 $i$를 만들 때 고른 확장 방향이다. S는 북쪽, I는 동쪽, Z는 서쪽, J는 남쪽이다.

$N$개의 줄을 출력한다. $i$번째 줄에는 구역 $i$의 승차권 가격을 출력한다.