More or Less Accurate

Time limit1sMemory limit256 MB

Summary

Add one to each negabinary number in the input and print the result without leading zeros.

Level: Medium5 of 10
Topics: Math, String, Simulation
Solved: No attempts yet

Problem

Each input line is an integer X in negabinary (base -2). Print X+1 in negabinary without leading zeros. Only zero itself may be written as a single 0.

Input

Several lines, each a string of bits 0 and 1. For nonzero values the most significant bit is 1.

Output

For each line, print X+1 in negabinary with no leading zeros.

Examples5

Example 1
Input
```
1
0
100
11
10101
```
Expected output
```
110
1
101
0
1101010
```
Example 2
Input
```
10
```
Expected output
```
11
```
Example 3
Input
```
110
```
Expected output
```
111
```
Example 4
Input
```
1111
```
Expected output
```
1100
```
Example 5
Input
```
1010
```
Expected output
```
1011
```