Задача E. Замена скобок: минимизация шагов ≡

Условие

Рассмотрим последовательность из открывающихся и закрывающихся круглых скобок. Назовём такую последовательность скобочной. Скобочная последовательность называется правильной, если она может быть построена по следующим законам:

• пустая строка является правильной скобочной последовательностью;
• если S — правильная скобочная последовательность, то (S) — тоже правильная скобочная последовательность.
• если A и B — правильные скобочные последовательности, то AB — тоже правильная скобочная последовательность.

Примеры правильных скобочных последовательностей — "()", "((()))", "()()()", "((()())())(())". Неформально говоря, правильная скобочная последовательность — это последовательность скобок, которая может быть получена из некоторого арифметического выражения удалением из него всего, кроме скобок.

Рассмотрим следующий алгоритм: на каждом шаге выбирается подстрока скобочной последовательности и скобки в ней меняются на противоположные, то есть все символы '(' в этой подстроке заменяются на ')', а все символы ')' — на '('.

Требуется написать программу, которая по скобочной последовательности рассчитает минимальное количество шагов N, необходимое для превращения её в правильную.

Формат входного файла

Во входном файле содержится скобочная последовательность.

Формат выходного файла

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

Если решения не существует, выведите единственное число −1.

Ограничения

Длина исходной последовательности находится в диапазоне от 1 до 3000 символов

Примеры тестов

()

0

))((()

1
1 4

)((()((()((()(((

2
1 16
2 7