| Author: | M. Sporyshev | Time limit: | 1 sec | |
| Input file: | input.txt | Memory limit: | 256 Mb | |
| Output file: | output.txt |
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 contains N characters 0 and 1 — King's sequence.
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.
1 ≤ N ≤ 105
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|