https://stackoverflow.com/questions/45658828/number-of-ways-to-merge-2-parenthesis-sequences。现在你可以在大约 $10^{18}$ 年内解决一个更难的问题。这几乎符合时间限制。你只需要做一些微小的优化。

如果两个括号序列 $s$ 和 $t$ 可以交错合并形成一个合法的括号序列，则称它们是可合并的（mergeable）。正式地，如果 $s$ 的长度为 $n$，$t$ 的长度为 $m$，当且仅当存在一个长度为 $n+m$ 的合法括号序列 $p$，以及两个长度分别为 $n$ 和 $m$ 的互不相交的下标序列 $a$ 和 $b$，满足以下条件时，它们是可合并的：

1. $0 \le a_1 < a_2 < \dots < a_n < n + m$
2. $0 \le b_1 < b_2 < \dots < b_m < n + m$
3. 对于所有 $i$，$p_{a_i} = s_i$
4. 对于所有 $i$，$p_{b_i} = t_i$

某个字符串的 RLE（行程长度编码，Run Length Encoding）是一个由二元组 $(c_i, a_i)$ 组成的列表，其中 $c_i$ 是一个字符，$a_i$ 是一个正整数，且对于任意 $i$ 满足 $c_i \neq c_{i+1}$。该编码的长度（即列表中二元组的个数）称为该字符串的行程长度（run length）。RLE 列表 $[(c_1, a_1), (c_2, a_2), \dots, (c_n, a_n)]$ 对应的原始字符串由 $a_1$ 个重复的字符 $c_1$、紧接着 $a_2$ 个重复的字符 $c_2$、依此类推，最后以 $a_n$ 个重复的字符 $c_n$ 结尾。可以证明，任何字符串的 RLE 都是唯一的。

给你一个括号序列 $s$ 的 RLE，以及 $m$ 个其他候选括号序列 $t_i$ 的 RLE。对于每个 $i$，判断 $t_i$ 和 $s$ 是否是可合并的。

输入格式

输入首先包含对序列 $s$ 的描述。第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$），表示 $s$ 的行程长度。

接下来 $n$ 行。其中第 $i$ 行描述 $s$ 的 RLE 中的一个二元组，包含一个字符 $c_i$ 和一个整数 $a_i$，中间用单个空格分隔（$c_i \in \{(, )\}$，$c_i \neq c_{i+1}$，$1 \le a_i \le 10^{12}$）。

下一行包含一个整数 $m$（$1 \le m \le 3 \cdot 10^5$），表示需要检查的序列 $t$ 的数量。

接下来的行依次描述这些序列，格式与 $s$ 的描述相同。如果对此不清楚，可以参考样例。

保证这 $m$ 个序列的行程长度之和不超过 $3 \cdot 10^5$。

输出格式

输出 $m$ 行。

第 $i$ 行如果 $t_i$ 和 $s$ 可合并，则输出 1，否则输出 0。

样例

输入样例 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