C. Генератор Деревьев™
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сов Пачино всегда интересовался деревьями — невзвешенными подвешенными деревьями, если быть точным. Он любит определять диаметр каждого дерева, что видит — максимальную длину простого пути в дереве.

Друзья Сова Пачино решили подарить ему Генератор Деревьев™ — мощное устройство, позволяющее создавать деревья по их описанию. Подвешенное дерево из $$$n$$$ вершин может быть описано скобочной последовательностью длины $$$2(n - 1)$$$ следующим образом: рассмотрим любой обход дерева, который начинается и заканчивается в корне, и проходит по каждому ребру ровно два раза — один раз вниз по дереву, другой раз вверх. Затем в порядке пути выпишем «(» (открывающую скобку) если по ребру прошли вниз, и «)» (закрывающую скобку), иначе.

На следующей иллюстрации расположены примеры подвешенных деревьев и их описания:

Сов выписал описание подвешенного дерева из $$$n$$$ вершин. Затем, он изменил его описание $$$q$$$ раз. Каждый раз, когда он выписывал новое описание, он выбирал два разных символа в описании, которое он написал в прошлый раз, менял их местами и записывал полученную строку. Он всегда следил за тем, чтобы каждая записанная строка была описанием подвешенного дерева.

Затем Пачино использовал Генератор Деревьев™ для каждого описания, которое он выписал. Какие диаметры у всех построенных деревьев?

Входные данные

В первой строке записано два целых числа $$$n, q$$$ ($$$3 \le n \le 100\,000$$$, $$$1 \le q \le 100\,000$$$) — количество вершин в дереве и количество изменений описания дерева.

Во второй строке записано описание исходного дерева — строка длины $$$2(n-1)$$$, состоящая из открывающих и закрывающих скобок.

В каждой из следующих $$$q$$$ строк записаны пары целых чисел $$$a_i, b_i$$$ ($$$2 \leq a_i, b_i \leq 2n-3$$$) обозначающих позиции двух скобок, которые меняются местами. Вы можете предполагать, что описание каждый раз изменится и что по этому описанию можно будет построить дерево.

Выходные данные

Выведите $$$q + 1$$$ целых чисел — диаметр каждого построенного по описанию дерева, в порядке, в котором эти описания выписывались.

Примеры
Входные данные
5 5
(((())))
4 5
3 4
5 6
3 6
2 5
Выходные данные
4
3
3
2
4
4
Входные данные
6 4
(((())()))
6 7
5 4
6 4
7 4
Выходные данные
4
4
4
5
3
Примечание

На следующей иллюстрации изображены все построенные деревья и их описания из первого примера: