Задача C. Замена скобок: выполнение алгоритма

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Во второй строке содержится число N.

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

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

В выходном файле должна содержаться единственная строка — результат работы алгоритма.

Ограничения

1 ≤ N, L ≤ 105

1 ≤ li ≤ ri ≤ L

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

Входной файл (input.txt) Выходной файл (output.txt)
1
(((((
1
1 5 
)))))
2
((())(()
3
1 8
2 6
4 7
)(((()((

0.037s 0.008s 15