Ngủ gật trong giờ học

Olga đang mơ thấy mình đứng trên một cầu thang có $n$ bậc, đánh số từ $1$ (bậc thấp nhất) đến $n$ (bậc cao nhất). Phía trên mỗi bậc có một mũi tên chỉ hướng — U (lên) hoặc D (xuống).

Mỗi giây Olga di chuyển một bước theo hướng của mũi tên ở bậc cô đang đứng tại đầu giây đó. Ngay sau khi cô rời khỏi một bậc, mũi tên trên bậc vừa rời sẽ đổi chiều: U thành D và D thành U.

Olga tỉnh dậy ngay khi cô bước ra khỏi cầu thang, tức là khi cô đi xuống từ bậc $1$ hoặc đi lên từ bậc $n$. Bản thân bước đi ra ngoài cũng tốn $1$ giây — ví dụ, nếu cô đang ở bậc $1$ và mũi tên là D, cô sẽ tỉnh dậy sau đúng $1$ giây.

Với mỗi bậc $i$, hãy xác định giấc mơ kéo dài bao nhiêu giây nếu Olga bắt đầu giấc mơ tại bậc đó. Nếu Olga sẽ không bao giờ rời khỏi cầu thang, hãy in $-1$.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên $n$ — số bậc của cầu thang.
• Dòng thứ hai chứa xâu $s$ độ dài $n$ gồm các kí tự U và D. Kí tự thứ $i$ của $s$ là hướng ban đầu của mũi tên trên bậc thứ $i$.

Dữ liệu ra

In $n$ số nguyên trên cùng một dòng, cách nhau bởi dấu cách: số thứ $i$ là độ dài giấc mơ khi Olga bắt đầu ở bậc $i$, hoặc $-1$ nếu cô không bao giờ ra khỏi cầu thang.

Ràng buộc

• $1\le n\le {10}^6$
• $s$ chỉ gồm các kí tự U và D.

Ví dụ