수직선 위에 $n$마리의 개미가 서 있으며, $i$번째 개미는 위치 $i$에 있습니다. 각 개미는 오른쪽(좌표가 증가하는 방향) 또는 왼쪽(좌표가 감소하는 방향)을 바라보고 있습니다. 개미는 매우 작아서 하나의 점으로 간주할 수 있습니다.

신호가 울리면 모든 개미는 동일한 단위 속도로 자신이 바라보는 방향으로 걷기 시작합니다. 두 개미가 충돌하면(같은 위치에 도달하면) 서로 튕겨 나가며, 즉 두 개미 모두 이동 방향을 바꾸어 계속 이동합니다. 일정 시간이 지나면 더 이상 충돌이 발생하지 않음이 증명되어 있습니다. 각 개미가 다른 개미와 몇 번 충돌하는지 계산하는 프로그램을 작성할 수 있습니까?

입력

첫 번째 줄에는 개미의 수를 나타내는 정수 $n$ ($1 \le n \le 300\,000$)이 주어집니다.

두 번째 줄에는 'L'과 'P'로만 구성된 길이 $n$의 문자열이 주어집니다. $i$번째 문자가 'L'이면 $i$번째 개미는 처음에 왼쪽을 바라보고 있고, 'P'이면 오른쪽을 바라보고 있습니다.

출력

한 줄에 $n$개의 정수를 공백으로 구분하여 출력합니다. $i$번째 숫자는 $i$번째 개미가 충돌한 횟수여야 합니다.

예제

입력 1

6
LPPLPL

출력 1

0 1 3 3 2 1

참고

첫 번째 개미는 처음에 왼쪽을 바라보고 있으며 다른 개미와 절대 충돌하지 않습니다. 마지막 개미는 5.5 지점에서 다섯 번째 개미와 충돌한 후 오른쪽으로 이동하기 시작하며 다시는 충돌하지 않습니다. 세 번째 개미는 3.5 지점에서 네 번째 개미와 충돌한 후 왼쪽으로 이동하기 시작합니다. 두 번째 개미는 3 지점에서 세 번째 개미와 충돌한 후 왼쪽으로 방향을 바꾸어 계속 이동합니다.