F. XOR Partitiontime limit per test7 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputFor 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.InputThe 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.OutputPrint 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.ExamplesInput542 13 1337 37 152Output10001Input41 2 3 4Output1100Input21 2Output10Input87 6 5 4 3 2 1 0Output10010110
Input542 13 1337 37 152
Output10001
['binary search', 'bitmasks', 'data structures', 'divide and conquer', 'greedy', 'trees', '*2700']