Problem Description

Xiao Lan manages a row of shelves, and there is a tag hanging in front of each shelf. Each tag contains the character $0$ or $1$, forming a string $S$ of length $N$ from left to right.

Xiao Lan can perform any number of tag-swapping operations, or perform none. One tag-swapping operation is done as follows:

• Choose two non-overlapping consecutive segments in the current tag sequence.
• The two consecutive segments must contain the same number of tags (i.e., have the same length).
• The numbers of tags with $1$ in the two segments must be the same.
• Swap the contents of the two segments in place. The other tags remain unchanged, and the relative order inside each segment remains unchanged.

For example, in the string $101001$, you can choose the segment $10$ and the segment $01$. Both have length $2$, and both contain one character $1$, so they can be swapped.

For two strings of the same length, compare them by the usual lexicographic order, and assume that $0$ is smaller than $1$.

Now, please find the lexicographically smallest string that Xiao Lan can obtain after any number of valid tag-swapping operations.

Input Format

The first line contains an integer $N$, representing the length of the string.

The second line contains a string $S$ of length $N$, consisting only of characters $0$ and $1$.

Output Format

Output one line containing a string of length $N$, representing the lexicographically smallest string that can be obtained.

6
101001

011010

5
00000

00000

8
11110000

11110000

Hint

Sample Explanation 1

You can choose the segment formed by the $1$st to $2$nd characters of the original string, which is $10$, and the segment formed by the $5$th to $6$th characters, which is $01$. These two segments have the same length and both contain one character $1$. After swapping them, you get $011010$.

It can be proven that among all reachable strings, $011010$ is lexicographically the smallest.

Sample Explanation 2

There is no character $1$ in the string, so any valid operation will not change the string.

Sample Explanation 3

In the original string, to the left of each character $0$ there are $4$ characters $1$. Under the constraints that valid operations must satisfy, it is impossible to obtain a lexicographically smaller string.

Constraints and Notes

For $30\%$ of the testdata, $1 \le N \le 10$.

For $60\%$ of the testdata, $1 \le N \le 5000$.

For all testdata, $1 \le N \le 2 \times 10^5$, and $S$ consists only of characters $0$ and $1$.

Translated by ChatGPT 5