Строка называется скобочной последовательностью, если она не содержит никаких символов, кроме «(» и «)». Скобочная последовательность называется правильной (кратко, ПСП), если из нее возможно получить корректное арифметическое выражение, вставляя символы «+» и «1». Например, «», «(())» и «()()» являются ПСП, а «)(» и «(()» не являются ПСП.
Легко заметить, что в ПСП каждой открывающей скобке ставится в пару некоторая закрывающая скобка. Используя данный факт, можно определить вложенность ПСП как максимальное количество пар скобок, таких, что \(2\)-я пара лежит внутри \(1\)-й, \(3\)-я — внутри \(2\)-й, и так далее. Например, вложенность «» равна \(0\), «()()()» — \(1\) и «()((())())» — \(3\).
Теперь, вам задана ПСП \(s\) четной длины \(n\). Вам нужно покрасить каждую скобку \(s\) в один из двух цветов: красный или синий. Скобочная последовательность \(r\), состоящая только из красных скобок, должна быть ПСП, а также скобочная последовательность \(b\), состоящая только из синих скобок, должна быть ПСП. Любая из них может быть пустой. Вам запрещается менять местами символы в \(s\), \(r\) или \(b\). Все скобки должны быть покрашены.
Среди всех возможных вариантов вы должны выбрать такой, что минимизирует максимум из вложенности \(r\) и \(b\). Если существует несколько ответов, вы можете вывести любой.
Выходные данные
Выведите единственную строку \(t\) длины \(n\), состоящую из «0» и «1». Если \(t_i\) равно «0», то символ \(s_i\) принадлежит ПСП \(r\), иначе \(s_i\) принадлежит \(b\).
Примечание
В первом примере одно из оптимальных решений следующее: \(s = \) «\(\color{blue}{()}\)». \(r\) — пустое и \(b = \) «\(()\)». Ответ равен \(\max(0, 1) = 1\).
Во втором примере выгодно сделать, например, \(s = \) «\(\color{red}{(}\color{blue}{(}\color{red}{)}\color{blue}{)}\)». \(r = b = \) «\(()\)» и ответ равен \(1\).
В третьем примере можно сделать \(s = \) «\(\color{red}{(}\color{blue}{((}\color{red}{)()}\color{blue}{)())}\)». \(r = \) «\(()()\)» и \(b = \) «\((()())\)», и ответ равен \(2\).