회전

바이트맨은 산으로 드라이브를 떠났다. 지도를 챙겨 왔지만, 지금 지도 위 어디에 있는지 알 수 없다.

지도에서 도로는 $n$개의 회전으로 이루어지며, 각 회전은 왼쪽 또는 오른쪽으로의 90° 회전이다. 도로 전체는 L(왼쪽 회전)과 P(오른쪽 회전)로 이루어진 길이 $n$의 문자열로 나타낸다. (P는 오른쪽을 뜻하는 폴란드어 "prawo"에서 왔다.)

바이트맨은 어떤 회전, 즉 $i$번째 회전 앞에 서 있지만, 그 $i$ 값이 무엇인지는 모를 수 있다. $a_i$를 그가 $i$번째 회전에서 출발하여 지도 위 어느 회전 앞에 있었는지 확신하기까지 지나가야 하는 회전의 수라고 하자.

그는 회전을 지나기 전에도 그 회전의 방향을 볼 수 있고, 지나간 뒤에는 다음 회전의 방향을 본다. 도로의 끝에 닿는 것 역시 하나의 정보다. 이런 관찰을 종합하면 자신이 있을 수 있는 위치가 점점 좁혀진다.

예를 들어 도로가 LLPPLPL이라고 하자. 바이트맨이 두 번째 회전 앞에 서 있다면, 지나기 전에는 왼쪽 회전이 보이므로 1, 2, 5, 7번 회전(모두 L인 위치) 중 하나 앞에 있을 수 있다. 그 회전을 지나면 오른쪽 회전 P가 보이는데, 이는 1번에서 출발한 경우(다음 회전이 L)와 7번에서 출발한 경우(바로 뒤에서 도로가 끝남)를 제외하여, 현재 위치로 3번 또는 6번만 남긴다. 회전 하나를 더 지나면 다시 P가 보이고, 이는 5번에서 출발한 분기를 제외하므로, 그는 이제 확실히 네 번째 회전 앞에 있다. 회전 두 번이면 충분했으므로 $a_2 = 2$이다.

도로의 설명을 읽고 모든 $1 \le i \le n$에 대해 $a_i$를 출력하는 프로그램을 작성하라.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 500\,000$). 둘째 줄에는 도로의 설명이 주어지는데, 공백 없이 L 또는 P로 이루어진 $n$개의 문자다.

정확히 $n$개의 줄을 출력한다. $i$번째 줄에는 정수 $a_i$ 하나를 출력한다.