Problem B. Binary king

Author:M. Sporyshev
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb

Statement

Young game developer Alice has created a new game and sent it to friends for beta-testing.

Young gamer Vasya wants to impress Alice by finishing the game completely.

At the final level Vasya fights the main boss — Binary King. At the beginning of the fight, Binary King generates a sequence K of N binary digits. After that, Vasya must present his own binary sequence V of the same length.

Vasya's sequence is scored as follows. For each position i, if Vi = 1 and Ki = 0, Vasya gains 1 point; if Vi = 0 and Ki = 1, Vasya loses 2 points.

Since Vasya plays at the hardest difficulty, each prefix of his sequence must contain at least as many zeroes as ones.

To win, Vasya must get maximum possible number of points.

Input file format

Input file contains N characters 0 and 1 — King's sequence.

Output file format

Output file must contain N characters 0 and 1 — Vasya's sequence scoring maximum number of points. If there are several optimal solutions, output any of them.

Constraints

1 ≤ N ≤ 105

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
111111111111
000000111111
2
111011001000
001011001011

0.025s 0.008s 9