Андрей любит строки, которые состоят из круглых скобок, но еще больше он любит заменять скобки на точки.

У него есть строка длины N, к которой он применяет M операций. Каждая операция задается двумя натуральными числами l_i и r_i, в результате операции в подстроке s_lis_li + 1, ..., s_ri самая длинная правильная скобочная подпоследовательность (далее ПСП) заменяется на точки (каждая скобочка заменяется на точку).

Андрей хочет себя проверить и просит вас помочь ему: подсчитать сколько скобок после каждой операции были заменены на точки.

Если в подстроке есть несколько ПСП максимальной длины, то выбирается наименьшая. Правило сравнения следующие: пусть a₁, a₂, ... , a_l  — позиции открывающихся скобок первой ПСП, а c₁, c₂, ..., c_l  — позиции открывающихся скобок второй ПСП. Считается, что первая ПСП меньше второй, если существует k (1 ≤ k ≤ l), такое что a_i = c_i (1 ≤ i < k) и a_k > c_k.

Если позиции открывающихся скобок обоих ПСП совпали, то сравниваются позиции закрывающихся скобок по следующему правилу: пусть b₁, b₂, ..., b_l  — позиции закрывающихся скобок первой ПСП, а d₁, d₂, ..., d_l  — позиции закрывающихся скобок второй ПСП. Считается, что первая ПСП меньше второй, если существует k (1 ≤ k ≤ l), такое что b_i = d_i (1 ≤ i < k) и b_k < d_k.