A garland is a chain of elements: flags and balls, containing at least one flag. The length of a garland is the number of elements it consists of.
A garland is considered beautiful if, for every flag, the number of consecutive balls to its left (up to the nearest flag to the left or the beginning of the garland) is equal to the number of consecutive balls to its right (up to the nearest flag to the right or the end of the garland).
Let us denote a ball with the symbol '0' and a flag with the symbol '1'. For example, the garland "0001000" is beautiful, while the garland "001010" is not, because there are two balls to the left of the first flag and one ball to its right. Note that the chain "000" is not a garland, as it does not contain any flags.
Given a garland, you are allowed to remove some of its elements. You are required to write a program that finds the longest beautiful garland that can be obtained from the given one by removing elements.
Input
The first line contains an integer $n$ — the number of elements in the original garland ($1 \leqslant n \leqslant 500\,000$).
The second line contains the description of the garland as a string of $n$ characters '0' and '1'. The string contains at least one '1'.
Output
In the first line, output the integer $m$ — the length of the resulting beautiful garland ($1 \leqslant m \leqslant n$).
In the second line, output the resulting beautiful garland.
If there are multiple solutions, output any one of them.
Subtasks
Let $k$ be the number of flags in the original garland.
| Subtask | Points | $n$ | $k$ | Required Subtasks |
|---|---|---|---|---|
| 1 | 20 | $n \leqslant 15$ | Yes | |
| 2 | 20 | $n \leqslant 1000$ | $k \leqslant 2$ | — |
| 3 | 20 | $n \leqslant 1000$ | $k \leqslant 15$ | Yes, 1, 2 |
| 4 | 16 | $n \leqslant 1000$ | Yes, 1–3 | |
| 5 | 10 | $n \leqslant 100\,000$ | $k \leqslant 50$ | Yes, 1–3 |
| 6 | 14 | $n \leqslant 500\,000$ | Yes, 1–5 |
Examples
Input 1
10 0100100000
Output 1
7 0001000
Input 2
3 111
Output 2
3 111
Input 3
7 0100101
Output 3
5 01010