Разработка текстового редактора — непростая задача. Ваша задача реализовать вспомогательный модуль для подсистемы подсветки скобок в тексте.

Ваш редактор состоит из строки бесконечной длины и курсора, который указывает на текущий символ. Обратите внимание, что он указывает точно на один из символов (а не между парой символов). Таким образом, положение курсора характеризуется индексом символа, на который он указывает. Пользователь может двигать курсор влево или вправо на одну позицию. Если курсор уже находится на первом (самом левом) символе, то сдвиг влево не производится.

Изначально все символы строки равны пробелу, курсор находится в первой (самой левой) позиции.

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

Ваш редактор должен уметь проверять, является ли текущая строка, набранная пользователем, «корректным текстом». Текст является корректным, если скобки в нём образуют правильную скобочную последовательность.

Формально, корректный текст (КТ) должен удовлетворять следующим правилам:

• любая строка без скобок является КТ (строка может содержать пробелы);
• если первый символ строки — это '(', последний — это ')', а все остальные (промежуточные) образуют КТ, то вся строка является КТ;
• два подряд написанных КТ также являются КТ.

Примеры корректных текстов: «hello(codeforces)», «round», «((i)(write))edi(tor)s», «( me)». Примеры текстов, которые не являются корректными: «hello)oops(», «round)», «((me)».

Пользователь использует специальные команды для работы с вашим редактором. Каждой команде соответствует свой символ, который нужно нажать, чтобы выполнить эту команду.

Соответствие команд и символов следующее:

• 'L' — сдвинуть курсор на один символ влево (остаётся на месте, если уже указывает на первый символ);
• 'R' — сдвинуть курсор на один символ вправо;
• любая строчная английская буква или круглая скобка '(' или ')' — записать введённый символ в позицию, на которой сейчас стоит курсор.

Для полного понимания изучите первый пример и его иллюстрации в примечании ниже.

Вам дана строка, содержащая символы, которые вводил пользователь. Для работы подсистемы подсветки скобок Вам требуется после каждой команды:

• проверить, является ли текущий текст в редакторе корректным;
• если является, то вывести наименьшее количество цветов, в которые можно раскрасить все пары скобок.

Если две пары скобок являются вложенными (первая во вторую или наоборот), то эти пары скобок должны быть раскрашены в разные цвета. Если две пары скобок не вложены, то они могут быть покрашены как в разные, так и в одинаковые цвета. Например, для скобочной последовательности «()(())()()» наименьшее количество цветов равно $$$2$$$, а для для скобочной последовательности «(()(()())())(())» — равно $$$3$$$.

Напишите программу, которая выводит требуемую информацию после обработки каждой команды.