Xâu nhị phân của Kirk

Cho xâu nhị phân $s$ (chỉ gồm các ký tự 0 và 1) có độ dài $n$. Hãy tìm xâu nhị phân $t$ cùng độ dài thỏa mãn đồng thời hai điều kiện:

• Với mọi cặp $l,r$ ($1\le l\le r\le n$), độ dài dãy con không giảm dài nhất của đoạn $s_l{s}_{l+1}\dots s_r$ bằng độ dài dãy con không giảm dài nhất của đoạn $t_l{t}_{l+1}\dots t_r$;
• Số lượng chữ số 0 trong $t$ là lớn nhất có thể.

Một dãy con không giảm của xâu $p$ là một dãy chỉ số $i_1<i_2<\dots <i_k$ sao cho $p_{i_1}\le p_{i_2}\le \dots \le p_{i_k}$. Độ dài của dãy con là $k$.

Nếu có nhiều xâu $t$ thỏa mãn, in ra một xâu bất kỳ.

Dữ liệu vào

Một dòng duy nhất chứa xâu nhị phân $s$.

Dữ liệu ra

In ra xâu nhị phân $t$ thỏa mãn các điều kiện trên.

Ràng buộc

• $1\le n\le {10}^5$.

Ví dụ