310546: CF1849F. XOR Partition

F. XOR Partitiontime limit per test7 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

For a set of integers $S$, let's define its cost as the minimum value of $x \oplus y$ among all pairs of different integers from the set (here, $\oplus$ denotes bitwise XOR). If there are less than two elements in the set, its cost is equal to $2^{30}$.

You are given a set of integers $\{a_1, a_2, \dots, a_n\}$. You have to partition it into two sets $S_1$ and $S_2$ in such a way that every element of the given set belongs to exactly one of these two sets. The value of the partition is the minimum among the costs of $S_1$ and $S_2$.

Find the partition with the maximum possible value.

Input

The first line contains $n$ ($2 \le n \le 200000$) — the number of elements in the set.

The second line contains $n$ distinct integers $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i < 2^{30}$) — the elements of the set.

Output

Print a string $n$ characters 0 and/or 1 describing the partition as follows: the $i$-th character should be 0 if the element $a_i$ belongs to $S_1$, otherwise, that character should be 1.

If there are multiple optimal answers, print any of them.

ExamplesInput

5
42 13 1337 37 152

Output

10001

Input

4
1 2 3 4

Output

1100

Input

2
1 2

Output

10

Input

8
7 6 5 4 3 2 1 0

Output

10010110

题目大意：
题目名为“F. XOR 分区”。给定一个整数集合 S，定义其成本为集合中任意两个不同整数 x 和 y 的按位异或（XOR）的最小值；如果集合中元素少于两个，则其成本为 \(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, \dots, a_n\)（\(0 \le a_i < 2^{30}\)），表示集合的元素。
- 输出：
- 输出一个长度为 \(n\) 的字符串，由字符 '0' 和 '1' 组成，描述分区方式：如果元素 \(a_i\) 属于 \(S_1\)，则第 \(i\) 个字符为 '0'；否则为 '1'。
- 如果存在多个最优解，输出其中任意一个。题目大意： 题目名为“F. XOR 分区”。给定一个整数集合 S，定义其成本为集合中任意两个不同整数 x 和 y 的按位异或（XOR）的最小值；如果集合中元素少于两个，则其成本为 \(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, \dots, a_n\)（\(0 \le a_i < 2^{30}\)），表示集合的元素。 - 输出： - 输出一个长度为 \(n\) 的字符串，由字符 '0' 和 '1' 组成，描述分区方式：如果元素 \(a_i\) 属于 \(S_1\)，则第 \(i\) 个字符为 '0'；否则为 '1'。 - 如果存在多个最优解，输出其中任意一个。