저글링 공연단

컴퓨팅과 고급 서커스 기술을 함께 가르치는 국립 센터에서는 학생의 기술 시연을 적극 권장한다.

초보 공연자 $n$명이 한 줄로 서서 저글링 공연을 하고 있다. 안타깝게도 모두 실력에 자신이 없어서 공연이 힘겹다. 그래서 기회가 생기는 즉시 자기 몫을 줄여 공연을 쉽게 만들려고 한다.

공을 두 개 이상 든 저글러는 양옆의 이웃에게 공을 하나씩 던진다. 어느 한쪽에 이웃이 없으면 그 방향으로는 공을 무대 밖으로 던진다. 모든 저글러가 동시에 공을 던진다. 공을 두 개 이상 든 저글러가 한 명도 없으면 공연이 끝난다.

아래 그림은 이 과정을 나타낸다.

그림 1: 첫 번째 예제의 진행 과정. 저글러 $n = 8$명의 공연이다.

관객인 당신은 이 공연이 별로 인상적이지 않다. 하지만 공연이 끝났을 때 각 저글러에게 공이 몇 개 남는지는 궁금하다.

첫째 줄에 문자 0, 1, 2로만 이루어진 길이 $n$의 문자열 $s$가 주어진다 ($1 \le n \le 10^6$). $s$의 $i$번째 문자는 $i$번째 사람이 처음에 든 저글링 공의 개수이다.

문자 0과 1로 이루어진 길이 $n$의 문자열을 출력한다. $i$번째 문자는 공연이 끝났을 때 $i$번째 사람이 든 저글링 공의 개수이다.