Мова теслярів
Міжнародна компанія професійних теслярів (ICPC) є провідною будівельною компанією, відомою своїми експертами-теслярами. Що робить ICPC лідером, так це їхня унікальна мова.
Синтаксис цієї мови визначається контекстно-вільною граматикою (КСГ) наступним чином:
S -> SS | (S) | )S( | ε
Іншими словами, у цій мові права дужка може бути закрита лівою дужкою, а ліва дужка може бути закрита правою дужкою.
Олексій, аспірант, який вивчає лінгвістику, вирішив дослідити мову ICPC. Як перший крок, йому потрібно визначити, чи є текст добре сформованим у цій мові. Він звернувся до вас, талановитого програміста, з проханням створити програму для оцінки.
Запит Олексія полягає в наступному: спочатку у вас є порожній рядок S, і ви будуєте довший рядок, вставляючи послідовність '(' або ')' у рядок. Ви отримаєте q запитів, кожен з яких складається з трьох елементів (p, c, n), де p - це позиція для вставки, n - кількість символів для вставки, а c - це або '(' або ')', символ для вставки. Для кожного запиту ваша програма повинна вставити символ, повторений n разів, у p-ту позицію рядка S з початку. Після кожної операції вставки програма повинна вивести "Yes", якщо S належить мові, і "No", якщо S не належить мові.
Будь ласка, допоможіть Олексію в його дослідженні, інакше він не зможе закінчити коледж.
Вхідні дані
Перший рядок містить одне ціле число 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", якщо S не належить мові.