У Поликарпа имеется конечная последовательность из открывающихся и закрывающихся скобок. Чтобы не уснуть на лекции, Поликарп развлекается со своей последовательностью. Он умеет выполнять две операции:
- добавление любой скобки в любую позицию (в начало, в конец или между любыми двумя имеющимися скобками);
- циклический сдвиг — перемещение самой последней скобки из конца последовательности в начало.
Поликарп может применить к своей последовательности любое количество операций добавления и циклического сдвига в любом порядке. В результате он хочет получить правильную скобочную последовательность минимальной возможной длины. В случае если таких последовательностей несколько, Поликарпа интересует лексикографически наименьшая. Помогите ему найти такую последовательность.
Правильной скобочной последовательностью называется последовательность открывающихся и закрывающихся скобок, из которой путем добавления символов «1» и «+» можно получить корректное арифметическое выражение. Каждой открывающейся скобке должна соответствовать закрывающаяся. Например, последовательности «(())()», «()», «(()(()))» правильные, а «)(», «(()» и «(()))(» — нет.
Последовательность a1 a2... an лексикографически меньше последовательности b1 b2... bn, если найдется такой номер i от 1 до n, что ak = bk при 1 ≤ k < i и ai < bi. Считайте, что «(» < «)».
Выходные данные
Выведите правильную скобочную последовательность минимальной длины, которую Поликарп может получить при помощи своих операций. Если таких последовательностей несколько, выведите лексикографически наименьшую.
Примечание
Последовательность в первом примере уже является правильной, но чтобы получить лексикографически наименьший ответ, нужно выполнить четыре операции циклического сдвига. Во втором примере нужно добавить закрывающуюся скобку между второй и третьей скобками и совершить циклический сдвиг. Можно сначала совершить сдвиг, а потом добавить скобку в конце.