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

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

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

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

Последовательность a₁ a₂... a_n лексикографически меньше последовательности b₁ b₂... b_n, если найдется такой номер i от 1 до n, что a_k = b_k при 1 ≤ k < i и a_i < b_i. Считайте, что «(»  <  «)».