Tô Màu RBS Hai Màu

Một xâu chỉ gồm các ký tự "(" và ")" được gọi là xâu ngoặc. Xâu ngoặc được gọi là đúng (regular bracket sequence, viết tắt RBS) nếu có thể chèn thêm các ký tự "+" và "1" vào để thu được một biểu thức số học hợp lệ. Ví dụ "", "(())" và "()()" là các RBS, còn ")(" và "(()" thì không.

Trong một RBS, mỗi dấu ngoặc mở được ghép với đúng một dấu ngoặc đóng. Độ sâu lồng nhau của một RBS là số lớn nhất các cặp ngoặc lồng vào nhau: cặp thứ 2 nằm trong cặp thứ 1, cặp thứ 3 nằm trong cặp thứ 2, và cứ như vậy. Ví dụ độ sâu của "" là 0, của "()()()" là 1, và của "()((())())" là 3.

Cho một RBS $s$ có độ dài chẵn $n$. Bạn cần tô màu mỗi dấu ngoặc của $s$ bằng một trong hai màu: đỏ hoặc xanh. Xâu $r$ gồm các dấu ngoặc màu đỏ (giữ nguyên thứ tự trong $s$) phải là một RBS, và xâu $b$ gồm các dấu ngoặc màu xanh cũng phải là một RBS. Một trong hai xâu có thể rỗng. Không được đổi thứ tự các ký tự, và mỗi dấu ngoặc đều phải được tô màu.

Trong tất cả các cách tô hợp lệ, hãy chọn cách sao cho giá trị lớn nhất giữa độ sâu của $r$ và độ sâu của $b$ là nhỏ nhất. Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Dữ liệu vào

• Dòng đầu chứa số nguyên chẵn $n$: độ dài của $s$.
• Dòng thứ hai chứa RBS $s$ có độ dài $n$.

Dữ liệu ra

In ra một xâu $t$ độ dài $n$ gồm các ký tự "0" và "1". Nếu $t_i=0$ thì ký tự $s_i$ thuộc về $r$ (màu đỏ), ngược lại $t_i=1$ thì $s_i$ thuộc về $b$ (màu xanh).

Ràng buộc

• $2\le n\le 2·{10}^5$
• $n$ chẵn
• $s$ là một RBS.

Ví dụ