F. И снова правильная скобочная последовательность
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа имеется конечная последовательность из открывающихся и закрывающихся скобок. Чтобы не уснуть на лекции, Поликарп развлекается со своей последовательностью. Он умеет выполнять две операции:

  • добавление любой скобки в любую позицию (в начало, в конец или между любыми двумя имеющимися скобками);
  • циклический сдвиг — перемещение самой последней скобки из конца последовательности в начало.

Поликарп может применить к своей последовательности любое количество операций добавления и циклического сдвига в любом порядке. В результате он хочет получить правильную скобочную последовательность минимальной возможной длины. В случае если таких последовательностей несколько, Поликарпа интересует лексикографически наименьшая. Помогите ему найти такую последовательность.

Правильной скобочной последовательностью называется последовательность открывающихся и закрывающихся скобок, из которой путем добавления символов «1» и «+» можно получить корректное арифметическое выражение. Каждой открывающейся скобке должна соответствовать закрывающаяся. Например, последовательности «(())()», «()», «(()(()))» правильные, а «)(», «(()» и «(()))(» — нет.

Последовательность a1 a2... an лексикографически меньше последовательности b1 b2... bn, если найдется такой номер i от 1 до n, что ak = bk при 1 ≤ k < i и ai < bi. Считайте, что «(»  <  «)».

Входные данные

В первой строке содержится последовательность Поликарпа, состоящая из символов «(» и «)». Длина строки от 1 до 1 000 000.

Выходные данные

Выведите правильную скобочную последовательность минимальной длины, которую Поликарп может получить при помощи своих операций. Если таких последовательностей несколько, выведите лексикографически наименьшую.

Примеры
Входные данные
()(())
Выходные данные
(())()
Входные данные
()(
Выходные данные
(())
Примечание

Последовательность в первом примере уже является правильной, но чтобы получить лексикографически наименьший ответ, нужно выполнить четыре операции циклического сдвига. Во втором примере нужно добавить закрывающуюся скобку между второй и третьей скобками и совершить циклический сдвиг. Можно сначала совершить сдвиг, а потом добавить скобку в конце.