Украина имеет талант

Однажды Вася посмотрев "Украина имеет талант" решил, что он тоже обладает сверхъестественными способностями. Чтобы в этом убедиться, он попросил помощи своих друзей.

Вася очень быстро умеет определять правильность cкобочной последовательности, а чтобы все было действительно необычным, он решил запоминать все образованные во время эксперимента последовательности. Эксперимент состоял в следующем: друзья просят Васю вспомнить, какая была последовательность на каком-то предыдущем шаге, а затем удалить или вставить скобку в эту последовательность. Образовавшуюся последовательность друзья выписывают на новый лист, а Вася отвечает, корректна ли скобочная последовательность, или нет.

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

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

Первая строка содержит количество действий N (1 ≤ N ≤ 100000). В строке под номером i+1 содержится описание события:

• 1 k p c — в последовательность k (0 ≤ k < i), на позицию p вставить скобку c - "(" или ")";
• 2 k p — в последовательности k (0 ≤ k < i) удалить скобку в позиции p,

все номера запросов и позиции в последовательности начинаются с единицы.

Сначала последовательность пуста. Эта начальная копия (версия) имеет номер 0. Далее идет N строк, в каждой из которых описание очередного запроса. Формат запросов описан выше. При обработке j-го запроса новая версия получит номер j. Запросов к несуществующим версиям не будет (j > i).

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

Для каждого запроса в отдельной строке нужно вывести YES - если соответствующая скобочная последовательность является правильной, или NO - в противном случае.