Juggling Troupe

At the national centre for computing and advanced circus skills, technical demonstrations by students are strongly encouraged.

A troupe of $n$ novice performers is standing in a row, attempting to put on a juggling show. Unfortunately, none of them are confident in their craft, and they are struggling. So, as soon as an opportunity presents itself, they try to reduce their part in the performance to make the task easier.

Whenever a juggler holds more than one ball, they throw one ball to each of their neighbours. If a juggler has no neighbour in some direction, they throw that ball offstage instead. Everybody throws their balls simultaneously. The show ends when no juggler holds more than one ball.

The figure below illustrates this process.

Figure 1: The first sample, a performance with $n = 8$ jugglers.

As a member of the audience, you are not impressed by this performance. You do wonder, however, how many balls each juggler has left at the end of the show.

One line with a string $s$ of length $n$ ($1 \le n \le 10^6$) over the characters 0, 1 and 2. The $i$-th character of $s$ is the number of juggling balls initially held by the $i$-th person.

Output a string of length $n$ over the characters 0 and 1, whose $i$-th character is the number of juggling balls the $i$-th person holds at the end of the show.