Background

土拨鼠吉吉吉很疑惑, 究竟是0好还是1好?

Description

给定一个长度为 $n$ 的 $01$ 序列 $a$，你可以对其进行若干次操作。

对于一次操作，选择 $1\leq l\leq r\leq n$，将 $a_l,...,a_r$中的 0101 翻转。

例如，将 $1010010$ 翻转为 $0101101$。

请你构造一个序列 $b$，使得序列 $a$ 变为序列 $b$ 的最少操作次数最多。

Format

Input

输入共两行。

第一行输入一个正整数 $n$。

第二行输入长度为 $n$ 的 $01$ 序列 $a$。

Output

输出共一行，输出长度为 $n$ 的 $01$ 序列 $b$。

Samples

样例1

3
000

101

解释: $000$变为$101$的最少次数为$2$. 对于其他的$6$个序列$001, 010, 011, 100, 110, 111$, 最少的操作次数均为$1$.

样例2

5
01101

11000

Limitation

对于 $30\%$ 的数据，有 $1\leq n\leq 5$。

对于另外 $20\%$ 的数据，有 $1\leq n\leq 10$。

对于另外 $20\%$ 的数据，有 $1\leq n\leq 20$。

对于 $100\%$ 的数据，有 $1\leq n\leq 10^5$，$n$ 为奇数。

注意:

文件重定向: reverse.in, reverse.out