Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

greedy

*1500

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Bicolored RBS

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular (shortly, RBS) if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are RBS and ")(" and "(()" are not.

We can see that each opening bracket in RBS is paired with some closing bracket, and, using this fact, we can define nesting depth of the RBS as maximum number of bracket pairs, such that the $$$2$$$-nd pair lies inside the $$$1$$$-st one, the $$$3$$$-rd one — inside the $$$2$$$-nd one and so on. For example, nesting depth of "" is $$$0$$$, "()()()" is $$$1$$$ and "()((())())" is $$$3$$$.

Now, you are given RBS $$$s$$$ of even length $$$n$$$. You should color each bracket of $$$s$$$ into one of two colors: red or blue. Bracket sequence $$$r$$$, consisting only of red brackets, should be RBS, and bracket sequence, consisting only of blue brackets $$$b$$$, should be RBS. Any of them can be empty. You are not allowed to reorder characters in $$$s$$$, $$$r$$$ or $$$b$$$. No brackets can be left uncolored.

Among all possible variants you should choose one that minimizes maximum of $$$r$$$'s and $$$b$$$'s nesting depth. If there are multiple solutions you can print any of them.

Input

The first line contains an even integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of RBS $$$s$$$.

The second line contains regular bracket sequence $$$s$$$ ($$$|s| = n$$$, $$$s_i \in \{$$$"(", ")"$$$\}$$$).

Output

Print single string $$$t$$$ of length $$$n$$$ consisting of "0"-s and "1"-s. If $$$t_i$$$ is equal to 0 then character $$$s_i$$$ belongs to RBS $$$r$$$, otherwise $$$s_i$$$ belongs to $$$b$$$.

Examples

Input

2 ()

Output

11

Input

4 (())

Output

0101

Input

10 ((()())())

Output

0110001111

Note

In the first example one of optimal solutions is $$$s = $$$ "$$$\color{blue}{()}$$$". $$$r$$$ is empty and $$$b = $$$ "$$$()$$$". The answer is $$$\max(0, 1) = 1$$$.

In the second example it's optimal to make $$$s = $$$ "$$$\color{red}{(}\color{blue}{(}\color{red}{)}\color{blue}{)}$$$". $$$r = b = $$$ "$$$()$$$" and the answer is $$$1$$$.

In the third example we can make $$$s = $$$ "$$$\color{red}{(}\color{blue}{((}\color{red}{)()}\color{blue}{)())}$$$". $$$r = $$$ "$$$()()$$$" and $$$b = $$$ "$$$(()())$$$" and the answer is $$$2$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/13/2024 01:11:49 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|