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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, L ≤ 10⁵

1 ≤ l_i ≤ r_i ≤ L

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

(((((
1
1 5 

)))))

((())(()
3
1 8
2 6
4 7

)(((()((

Разбор

Очевидно, что в худшем случае время работы наивного алгоритма (честно моделирующего каждый шаг) равно Ο(N × L), что при данных ограничениях работает медленно.

Заметим, что при инвертировании скобки (замены на противоположную) чётное количество раз, скобка не меняется, а при нечётном — инвертируется. Следовательно для решения задачи необходимо и достаточно знать для каждой скобки чётность количества инвертирований. a[i] = p будет значить, что чётность инвертирования скобки i равна чётности числа p. Массив a, следует сначала обнулить, а далее заполнять так: считать очередные l, r,увеличиваем a[l] и a[r+1] на единицу. В переменной k будем хранить чётность количества инфертирований каждой буквы, на каждом шаге увеличивая k на a[i]. Время работы данного алгоритма равно Ο(N + L).

Фрагмент исходного кода:

procedure inv(var c: char); inline;
begin
  if c = ')' then c := '(' else c := ')';
end;
<…>
for i := 1 to n do
  begin
    read(fi, l, r);
    inc(a[l]); inc(a[r+1]);
  end;
k := 0;
for i := 1 to len do
  begin
    inc(k, a[i]);
    if k mod 2 = 1 then inv(s[i]);
  end;