Trên trục số có $n$ con kiến, con kiến thứ $i$ đứng tại vị trí $i$. Mỗi con kiến nhìn về bên phải (hướng tọa độ tăng dần) hoặc bên trái (hướng tọa độ giảm dần). Các con kiến nhỏ đến mức chúng ta có thể coi chúng là các điểm đơn lẻ.

Khi có tín hiệu, tất cả các con kiến bắt đầu di chuyển với cùng một vận tốc đơn vị theo hướng mà chúng đang nhìn. Nếu hai con kiến va chạm (ở cùng một vị trí), chúng sẽ bật ngược lại, nghĩa là cả hai đều đổi hướng di chuyển và tiếp tục đi. Có thể chứng minh rằng sau một khoảng thời gian nhất định, sẽ không còn va chạm nào xảy ra nữa. Bạn có thể viết chương trình tính toán xem mỗi con kiến sẽ va chạm với các con kiến khác bao nhiêu lần không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào tiêu chuẩn chứa một số nguyên $n$ ($1 \le n \le 300\,000$), biểu thị số lượng kiến.

Dòng thứ hai của dữ liệu vào tiêu chuẩn chứa một từ có độ dài $n$ chỉ bao gồm các ký tự 'L' và 'P'. Nếu ký tự thứ $i$ của từ này là 'L', con kiến thứ $i$ ban đầu nhìn về bên trái. Ngược lại, nếu ký tự là 'P', con kiến đó nhìn về bên phải.

Dữ liệu ra

Trên một dòng duy nhất của dữ liệu ra tiêu chuẩn, in ra $n$ số cách nhau bởi các khoảng trắng. Số thứ $i$ trong số đó phải bằng số lần va chạm của con kiến thứ $i$.

Ví dụ

Dữ liệu vào 1

6
LPPLPL

Dữ liệu ra 1

0 1 3 3 2 1

Ghi chú

Con kiến đầu tiên ban đầu nhìn về bên trái và sẽ không bao giờ va chạm với bất kỳ con kiến nào khác. Con kiến cuối cùng sẽ va chạm với con kiến thứ năm tại vị trí $5.5$, sau đó nó bắt đầu di chuyển về bên phải và không bao giờ dừng lại. Con kiến thứ ba, sau khi va chạm với con kiến thứ tư tại vị trí $3.5$, sẽ bắt đầu đi về bên trái. Con kiến thứ hai sẽ va chạm với nó tại vị trí $3$, sau đó nó quay sang trái và không bao giờ ngừng di chuyển.