Juggling Troupe

Time limit3sMemory limit512 MB

Summary

Simulate balls thrown left and right simultaneously until every position holds at most one ball, then report the final configuration.

Level: Hard8 of 10
Topics: Simulation, Greedy, Implementation, Math
Solved: No attempts yet

Problem

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.

Input

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

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.

Examples6

Example 1
Input
```
12100212
```
Expected output
```
10111111
```

Example 2

Input

000111222000222111222001

Expected output

111111101111111111111111

Example 3
Input
```
2
```
Expected output
```
0
```
Example 4
Input
```
1010
```
Expected output
```
1010
```
Example 5
Input
```
222
```
Expected output
```
101
```
Example 6
Input
```
2222
```
Expected output
```
1111
```