Язык плотников
Международная компания профессиональных плотников (ICPC) — ведущая строительная компания, известная своими опытными плотниками и уникальным языком.
Синтаксис этого языка описывается следующей КС-грамматикой:
S -> SS | (S) | )S( | ε
Это означает, что в этом языке правая скобка может быть закрыта левой, а левая — правой.
Алекс, аспирант, изучающий лингвистику, решил исследовать язык ICPC. Его первой задачей является определение, правильно ли сформирован текст на этом языке. Он попросил вас, как опытного программиста, создать программу для этой проверки.
Запрос Алекса таков: изначально у вас есть пустая строка S, и вы строите более длинную строку, вставляя в неё последовательности символов '(' или ')'. Вам будет дано q запросов, каждый из которых состоит из трёх элементов (p, c, n), где p — позиция для вставки, n — количество вставляемых символов, а c — символ '(' или ')'. Для каждого запроса ваша программа должна вставить символ c, повторяющийся n раз, в p-ю позицию строки S. После каждой операции вставки программа должна выводить "Yes", если S соответствует языку, и "No", если не соответствует.
Пожалуйста, помогите Алексу в его исследовании, иначе он не сможет окончить колледж.
Входные данные
Первая строка содержит одно целое число q (1 ≤ q ≤ 10^5), обозначающее количество запросов. Далее следуют q строк, каждая из которых содержит три элемента: p, c, n, разделённые пробелом (1 ≤ i ≤ q, c_i = '(' или ')', 0 ≤ p_i ≤ длина S до i-го запроса, 1 ≤ n ≤ 2^20). Гарантируется, что все запросы корректны.
Выходные данные
Для каждого запроса выводите "Yes", если S соответствует языку, и "No", если не соответствует.