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