对于一组整数$$$S$$$,我们将其成本定义为该组中所有不同整数对中$$$x \oplus y$$$ 的最小值(这里,$$$\oplus$$$ 表示按位异或)。如果集合中的元素少于两个,则其成本等于 $$$2^{30}$$$。
给你一组整数 $$$\{a_1, a_2, \dots, a_n\}$$$。您必须将其划分为两个集合 $$$S_1$$$ 和 $$$S_2$$$,使得给定集合的每个元素都恰好属于这两个集合之一。分区的值是$$$S_1$$$和$$$S_2$$$的成本中最小的。
查找具有最大可能值的分区。
输入
第一行包含 $$$n$$$ ($$$2 \le n \le 200000$$$) — 集合中的元素数量。
第二行包含 $$$n$$$ 不同的整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — 集合的元素。
输出
打印描述分区的字符串 $$$n$$$ 个字符 0 和/或 1,如下所示:如果元素 $$$a_i$$$ 属于 $$$S_1$$$,则第 $$$i$$$ 个字符应为 0,否则该字符应为 1。
如果有多个最佳答案,则打印其中任何一个。
示例
输入 #1
5 42 13 1337 37 152
输出 #1
10001
输入 #2
4 1 2 3 4
输出 #2
1100
输入 #3
2 1 2
输出 #3
10
输入#4
8 7 6 5 4 3 2 1 0
输出#4
10010110