목수의 언어

시간 제한1초메모리 제한512 MB

요약

매 질의마다 '(' 또는 ')'를 한 위치에 n개 삽입한 뒤, 전체 문자열이 문법 S -> SS | (S) | )S( | ε에 맞는 올바른 문장인지 판정한다.

난이도: 어려움10점 중 9점
유형: 문자열, 스택, 세그먼트 트리, 구현
정답자: 아직 제출이 없습니다

문제

International Carpenters Professionals Company (ICPC)는 숙련된 목수가 많은 최고의 건설 회사다. ICPC를 최고의 회사로 만드는 것은 이 회사만의 독자적인 언어다.

이 언어의 문법은 다음과 같이 CFG로 간단히 주어진다:

S -> SS | (S) | )S( | ε

즉, 이 언어에서는 오른쪽 괄호를 왼쪽 괄호로 닫을 수 있고 왼쪽 괄호를 오른쪽 괄호로 닫을 수 있다.

언어학을 전공하는 대학원생 Alex는 ICPC의 언어를 연구하기로 했다. 연구의 첫 단계로, 그는 어떤 텍스트가 이 언어에서 올바른 형식인지 판정해야 한다. 그래서 그는 훌륭한 프로그래머인 당신에게 이 판정을 위한 프로그램을 작성해 달라고 부탁했다.

Alex의 요청은 다음과 같다. 처음에 빈 문자열 S가 있고, 여기에 '(' 또는 ')'의 연속을 삽입해 더 긴 문자열을 만든다. $q$ 개의 질의가 주어지며, 각 질의는 세 요소 $(p, c, n)$ 으로 이루어진다. $p$ 는 삽입할 위치, $n$ 은 삽입할 문자 수, $c$ 는 삽입할 문자로 '(' 또는 ')' 중 하나다. 각 질의마다 S의 처음부터 $p$ 번째 위치에 $c$ 를 $n$ 번 반복해 삽입해야 한다. 또한 각 삽입 연산을 수행한 뒤 S가 이 언어에 속하면 "Yes"를, 속하지 않으면 "No"를 출력해야 한다.

Alex가 졸업하지 못하지 않도록, 그의 연구를 도와주자.

입력

첫째 줄에는 질의의 수를 나타내는 정수 $q$ ( $1 \leq q \leq 10^5$ )가 주어지고, 이어서 $q$ 개의 줄에 걸쳐 세 요소 $p_i$ , $c_i$ , $n_i$ 가 공백 하나로 구분되어 주어진다 ( $1 \leq i \leq q$ , $c_i =$ '(' 또는 ')', $0 \leq p_i \leq$ $i$ 번째 질의 전 S의 길이, $1 \leq n \leq 2^{20}$ ). 입력의 모든 질의는 유효함이 보장된다.

출력

각 질의마다 S가 이 언어에 속하면 "Yes"를, 속하지 않으면 "No"를 출력한다.

예제3

예제 1
입력
```
3
0 ( 10
10 ) 5
10 ) 5 
```
예상 출력
```
No
No
Yes
```
예제 2
입력
```
3
0 ) 10
10 ( 5
10 ( 5
```
예상 출력
```
No
No
Yes
```
예제 3
입력
```
3
0 ( 10
10 ) 20
0 ( 10
```
예상 출력
```
No
No
Yes
```