Xâu nhỏ nhất

Cho một xâu $s$ chỉ gồm hai loại ký tự a và b.

Ta xét lần lượt tất cả các tiền tố của $s$ có độ dài từ $1$ đến $|s|$, theo thứ tự từ ngắn nhất đến dài nhất. Với mỗi tiền tố, ta được phép đảo ngược tiền tố đó hoặc giữ nguyên. Các quyết định được thực hiện tuần tự: xử lý xong tiền tố độ dài $i$ mới chuyển sang tiền tố độ dài $i+1$, và mọi thao tác đảo ngược sau đó tác động lên xâu đã bị biến đổi bởi các thao tác trước.

Hãy chọn tập các tiền tố cần đảo ngược sao cho xâu thu được sau khi xét hết tất cả tiền tố là nhỏ nhất theo thứ tự từ điển.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ chỉ gồm các ký tự a và b.

Dữ liệu ra

In ra đúng $|s|$ số nguyên. Số thứ $i$ bằng $1$ nếu cần đảo ngược tiền tố độ dài $i$ (đoạn từ vị trí $1$ đến $i$), và bằng $0$ nếu ngược lại.

Nếu có nhiều cách cho ra kết quả tối ưu, in ra một cách bất kỳ.

Ràng buộc

• $1\le |s|\le 1000$
• $s$ chỉ gồm các ký tự a và b.

Ví dụ