시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB776100.000%

문제

U nizu mjera za unapređenje javnog prometa u glavnom gradu, prometno poduzeće odlučilo je promijeniti granice zona javnog prometa. Umjesto dosadašnjeg kružnog modela, prelazi se na romboidni model. Grad je podijeljen na N zona označenih brojevima 1 do N. Zona 1 je kvadrat duljine stranica 1 km sa središtem u samom centru grada. Zona 2 dobivena je širenjem kvadrata zone 1 u jednom od smjerova sjever, istok, zapad ili jug, tako mu duljina stranice bude 2 km. Svaka sljedeća zona dobiva se daljnjim širenjem kvadrata u jednom od navedenih smjerova, tako da se stranica svaki put produlji za 1 km.

Na slici je prikazana jedna moguća podjela grada na 4 zone: za zonu 2 odabran je smjer širenja na sjever, za zonu 3 na zapad, a za zonu 4 ponovno na sjever. 

Cijena karte u svakoj zoni odgovara broju susjednih zona koje ju okružuju. Cijene karata u gornjem primjeru su tako 2 kn u zoni 1, 3 kn u zoni 2, 3 kn u zoni 3 te 2 kn u zoni 4. 

입력

U prvom retku ulaza nalazi se broj N (2 ≤ N ≤ 300 000), broj zona.

U sljedećih N−1 redaka nalazi se jedno od slova 'S', 'I', 'Z', 'J'. Slovo u i-tom retku označava smjer širenja odabran za zonu i. 

출력

Potrebno je ispisati N redaka, po jedan za svaku zonu. U i-tom retku ispišite cijenu karte u i-toj zoni. 

예제 입력 1

4
S
Z
S

예제 출력 1

2
3
3
2

예제 입력 2

5
J
I
S
Z

예제 출력 2

3
4
4
4
3

예제 입력 3

5
S
J
S
J

예제 출력 3

2
3
4
3
2