시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB222100.000%

문제

https://stackoverflow.com/questions/45658828/number-of-ways-to-merge-2-parenthesis-sequences. Now you can solve a strictly harder problem in about $10^{18}$ years. This almost fits in the time limit. All you have to do is some minor optimizations.

Two sequences of parentheses $s$ and $t$ mergeable if they can be interleaved to form a balanced parentheses sequence. Formally, if $s$ has length $n$ and $t$ has length $m$ they are mergeable if and only if there exists a balanced parentheses sequence $p$ of length $n + m$, and two disjoint sequences of indices $a$ and $b$ of length $n$ and $m$ respectively, such that:

  1. $0 \leq a_1 < a_2 < \ldots < a_n < n + m$
  2. $0 \leq b_1 < b_2 < \ldots < b_m < n + m$
  3. For all $i$ $p_{a_i} = s_i$
  4. For all $i$ $p_{b_i} = t_i$

The RLE (Run Length Encoding) of some string is a list of pairs $(c_i, a_i)$ where $c_i$ is a character and $a_i$ is a positive integer and $\forall_i c_i \neq c_{i+1}$, the length of the encoding (i.e. number of pairs in the list) is called the run length of the string. The original string of RLE $[(c_1, a_1), (c_2, a_2), \ldots, (c_n, a_n)]$ consists of $a_1$ repetitions of character $c_1$, followed by $a_2$ repetitions of character $c_2$, and so on, and ends with $a_n$ repetitions of character $c_n$. It can be shown that RLE is unique.

You are given an RLE of a parentheses sequence $s$ and RLEs of $m$ other parentheses sequences candidates $t_i$.

For each $i$ find out if $t_i$ and $s$ are mergeable.

입력

The input starts with a description of the sequence $s$. The first line contains a single integer $n$ ($1 \leq n \leq 3 \cdot 10^5$), the run length of $s$.

$n$ lines follow. $i$-th of them describes a single pair in the RLE of $s$ and contains a character $c_i$ and an integer $a_i$ separated by a single space ($c_i \in \{ (, ) \}, c_i \neq c_{i+1}, 1 \leq a_i \leq 10^{12}$).

The next line contains a single integer $m$ ($1 \leq n \leq 3 \cdot 10^5$), the number of sequences $t$ to check.

The remaining lines describe those sequences one by one, using the same format as the description of $s$. If this isn't clear you should take a look at the samples.

It is guaranteed that the sum of run lengths of those $m$ sequences doesn't exceed $3 \cdot 10^5$. 

출력

Print $m$ lines.

The $i$-th of those lines should contain 1 if $t_i$ and $s$ are mergeable and 0 if they are not.

예제 입력 1

4
( 1
) 3
( 3
) 1
1
2
( 1
) 1

예제 출력 1

0

예제 입력 2

2
( 2
) 1
4
1
( 1
1
) 1
2
) 2
( 1
2
) 4
( 3

예제 출력 2

0
1
1
0

예제 입력 3

4
) 2
( 3
) 5
( 100
3
1
) 96
2
( 132
) 228
4
( 2
) 3
( 5
) 100

예제 출력 3

0
1
1

예제 입력 4

1
) 1000000000000
2
1
) 1000000000000
1
( 1000000000000

예제 출력 4

0
1