Вы устали от своей грязной комнаты, поэтому вы решили в ней прибраться.

Ваша комната это скобочная последовательность $$$s=s_{1}s_{2}\dots s_{n}$$$ длины $$$n$$$. Каждый символ этой строки это либо открывающая круглая скобка '(', либо закрывающая круглая скобка ')'.

За одну операцию вы можете выбрать любую подстроку строки $$$s$$$ и перевернуть ее. Формально, за одну операцию вы можете выбрать подстроку $$$s[l \dots r]=s_l, s_{l+1}, \dots, s_r$$$ и поменять порядок элементов в ней на $$$s_r, s_{r-1}, \dots, s_{l}$$$.

Например, если вы захотите перевернуть подстроку $$$s[2 \dots 4]$$$ строки $$$s=$$$«((()))», она станет равна $$$s=$$$«()(())».

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

Префиксом строки $$$s$$$ называется её подстрока, которая начинается с индекса $$$1$$$. Например, для строки $$$s=$$$«(())()» есть $$$6$$$ префиксов: «(», «((», «(()», «(())», «(())(» и «(())()».

По вашему мнению, красивая и чистая комната $$$s$$$ — это такая, что:

• вся строка $$$s$$$ целиком является правильной скобочной;
• и ровно $$$k$$$ ее префиксов(включая всю строку $$$s$$$) являются правильными скобочными.

Например, если $$$k = 2$$$, то «(())()» это красивая и чистая комната.

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

Гарантируется, что ответ существует. Обратите внимание, что вам не нужно минимизировать количество операций — найдите любой способ достичь требуемой конфигурации за $$$n$$$ или менее операций.