You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

B.递归(rec)

题目描述

递减括号序列是可以表示为 $(A_1)(A_2)...(A_k)$ ，且满足对 $1\le i\le k$ 有 $A_i$ 是递减括号序列，对 $1\le i<k$ 有 $A_i\ge A_{i+1}$ ，且 $k\ge 0$ 的字符串。比较两个递减括号序列时，按字符串的字典序比较，空串最小，'(' 比 ')' 大。

给定 $n$ 个非空的递减括号序列，两个玩家轮流操作，每次操作可以将某个非空的递减括号序列改为字典序更小的递减括号序列，不能操作者败。假设双方都使用最优策略且都希望对方败，对 $1\le k\le n$ 问如果仅保留前 $k$ 个递减括号序列，先手是否必胜。

输入格式

第一行一个整数 $n$ ；

接下来 $n$ 行，每行一个非空的递减括号序列。

输出格式

共 $n$ 行，第 $k$ 行表示保留前 $k$ 个递减括号序列时，先手是否必胜；是则输出 $1$ ，否则输出 $0$ 。

样例输入 #1

6
(())()()
(())()()
()()
()
()()()
((())(())()())(()()())

样例输出 #1

1
0
1
1
0
1

「样例 #2」

见题目附件下的 ex_rec/rec0_02.in 与 ex_rec/rec0_02.out。

该样例满足 $25\%$ 的条件限制。

「样例 #3」

见题目附件下的 ex_rec/rec0_03.in 与 ex_rec/rec0_03.out。

该样例满足 $50\%$ 的条件限制。

「样例 #4」

见题目附件下的 ex_rec/rec0_04.in 与 ex_rec/rec0_04.out。

该样例满足 $75\%$ 的条件限制。

「样例 #5」

见题目附件下的 ex_rec/rec0_05.in 与 ex_rec/rec0_05.out。

该样例满足 $100\%$ 的条件限制。

数据范围

对每个测试点，$1\le n\le 5\times 10^4$ ，字符串的总长不超过 $10^5$ 。

对于 $25\%$ 的数据，满足每行的字符串不包含子串 ((。

对于另外 $25\%$ 的数据，满足每行的字符串可以由 (()) 和 () 拼接得到。

对于另外 $25\%$ 的数据，满足每行的字符串不包含子串 (((。

对于另外 $25\%$ 的数据，无特殊限制。

大样例