Iron和Werewolf正在参加国际象棋奥林匹克比赛,所以他们想练习团队建设。他们聚集了$$$n$$$玩家,其中$$$n$$$是$$$2$$$的幂,他们会进行体育运动。 Iron 和 Werewolf 就属于这些 $$$n$$$ 人。
其中一项运动是拔河。对于每个 $$$1\leq i \leq n$$$,第 $$$i$$$ 个玩家的实力为 $$$s_i$$$。淘汰赛将持续到只剩下一名玩家为止——我们称该玩家为绝对获胜者。
每轮:
- 假设 $$$m>1$$$ 玩家仍在游戏中,其中 $$$m$$$ 是 $$$2$$$ 的幂。
- $$$m$$$ 玩家被分成大小相等的两队(即每队有 $$$m/2$$$ 玩家)。一支球队的实力是其球员实力的总和。
- 如果两队实力相当,则由 Iron 选择获胜者;否则,实力较强的球队获胜。
- 失败队伍中的所有玩家都被淘汰,因此 $$$m/2$$$ 玩家留下来。
Iron已经知道了每个选手的实力,他想知道谁能成为绝对的胜利者,谁不能成为绝对的胜利者,如果他可以选择每轮的队伍组成,以及实力相等的情况下获胜的队伍。
输入
第一行包含一个整数 $$$n$$$ ($$$4 \leq n \leq 32$$$) — 参加拔河比赛的玩家数量。保证 $$$n$$$ 是 $$$2$$$ 的幂。
第二行由整数序列 $$$s_1,s_2, \ldots, s_n$$$ ($$$1 \leq s_i \leq 10^{15}$$$) 组成——玩家的优势。
输出
在单行中输出长度为 $$$n$$$ 的二进制字符串 $$$s$$$ — 如果第 $$$i$$$ 位玩家能够成为绝对获胜者,则 $$$s$$$ 的第 $$$i$$$ 个字符应为 $$$1$$$,否则应为 $$$0$$$。
示例
输入 #1
4 60 32 59 87
输出 #1
1001
输入 #2
4 100 100 100 100
输出 #2
1111
输入 #3
8 8 8 8 8 4 4 4 4
输出 #3
11110000
输入#4
32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
输出#4
00000000000000001111111111111111
输入 #5
16 1 92875987325987 1 1 92875987325986 92875987325985 1 92875987325988 92875987325990 92875987325989 1 1 92875987325984 92875987325983 1 1
输出 #5
0100110111001000
注意
在第一个例子中,玩家$$$1$$$和$$$4$$$的实力分别为$$$60$$$和$$$87$$$可以成为绝对的赢家。
让我们描述一下玩家 $$$1$$$ 的过程。首先,我们将玩家分为$$$[1,3]$$$和$$$[2,4]$$$两队。这两支球队的优势是$$$60+59=119$$$ 和$$$32+87=119$$$。他们是平等的,Iron 可以选择取消两支球队中任何一支的资格。让他选择的是第二队。
我们剩下玩家 $$$1$$$ 和 $$$3$$$。由于 $$$1$$$ 具有更强的实力($$$60>59$$$),他们获胜并被宣布为绝对获胜者,因为他们是最后剩下的玩家。
在第三个示例中,其余玩家的优势可能类似于 $$$[8,8,8,8,4,4,4,4] \rightarrow [8,8,4,4] \rightarrow [8,4] \rightarrow [8]$$$。每个拥有$$$8$$$实力的人都可以成为绝对的胜利者,并且可以证明其他人不能。