Вы устали от своей грязной комнаты, поэтому вы решили в ней прибраться.
Ваша комната это скобочная последовательность \(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\) или менее операций.
Выходные данные
Для каждого из наборов входных данных выведите ответ.
В первой строке выведите число \(m\) (\(0 \le m \le n\)) — количество операций. Вам не требуется минимизировать \(m\), это число может быть любым.
В следующих \(m\) строках выведите описания операций, каждая строка должна содержать два целых числа \(l,r\) (\(1 \le l \le r \le n\)), описывающих операцию переворота подстроки \(s[l \dots r]=s_{l}s_{l+1}\dots s_{r}\). Операции выполняются последовательно одна за другой.
Итоговая строка \(s\) после применения всех операций должна быть правильной, ровно \(k\) её префиксов (включая \(s\)) должны быть правильными.
Гарантируется, что ответ существует. Если есть несколько возможных ответов, вы можете вывести любой.