Zones

To improve public transport in the capital, the transport company decided to change the boundaries of its fare zones. The old circular model is replaced by a rhombus model. The city is divided into $N$ zones numbered $1$ to $N$.

Zone $1$ is a square with side length $1$ km, centered at the very center of the city. The square is rotated by 45 degrees, so its four vertices point north, east, south, and west. Zone $2$ is obtained by expanding the square of zone $1$ in one of the directions north, east, west, or south so that its side length becomes $2$ km. Each following zone is obtained by expanding the square again in one of these four directions, and each expansion makes the side $1$ km longer. When the square is expanded in a direction, the new square contains the previous one and shares with it the vertex opposite the chosen direction. Zone $i$ ($i \ge 2$) is the region of the $i$-th square that lies outside the $(i-1)$-th square.

The figure below shows one possible division of the city into 4 zones: zone $2$ expands north, zone $3$ expands west, and zone $4$ expands north again.

The ticket price in each zone equals the number of zones that share a border with it. In the example above, the ticket price is 2 kuna in zone $1$, 3 kuna in zone $2$, 3 kuna in zone $3$, and 2 kuna in zone $4$.

Find the ticket price in every zone.

The first line contains $N$ ($2 \le N \le 300\,000$), the number of zones.

Each of the next $N-1$ lines contains one of the letters S, I, Z, J. The letter on input line $i$ ($2 \le i \le N$) is the expansion direction chosen for zone $i$: S is north, I is east, Z is west, and J is south.

Print $N$ lines. On the $i$-th line, print the ticket price in zone $i$.