Trò chơi xâu con

Mike và Ann chơi một trò chơi với xâu $s$ gồm các chữ cái latin in thường và một chỉ số $k$ ($0\le k<|s|$).

Ban đầu cặp biên $(l,r)=(k,k)$, nghĩa là xâu con đang xét là $s[l,r]=s[k]$. Hai người chơi luân phiên đi nước (Ann đi trước), mỗi nước là:

• Chọn $l^{\prime },r^{\prime }$ thoả $l^{\prime }\le l$, $r^{\prime }\ge r$ và xâu con $s[l^{\prime },r^{\prime }]$ nhỏ hơn $s[l,r]$ theo thứ tự từ điển. Cập nhật $l:=l^{\prime },r:=r^{\prime }$.

Người không thể đi nước hợp lệ sẽ thua. Cả hai chơi tối ưu.

Với mỗi $k$ từ $0$ đến $|s|-1$, hãy xác định ai là người thắng.

Dữ liệu vào

Một dòng duy nhất chứa xâu $s$ ($1\le |s|\le 5·{10}^5$) gồm các chữ cái latin in thường.

Dữ liệu ra

In ra $|s|$ dòng. Dòng thứ $i$ (đánh số từ $0$) in Ann nếu Ann thắng khi $k=i$, ngược lại in Mike.

Ràng buộc

• $1\le |s|\le 5·{10}^5$
• $s$ chỉ gồm chữ cái latin in thường.

Ví dụ