A13861 | Two Arrays

RedDreamer has an array $a$ consisting of $n$ non-negative integers, and an unlucky integer $T$ .

Let's denote the misfortune of array $b$ having length $m$ as $f(b)$ — the number of pairs of integers $(i, j)$ such that $1 \le i < j \le m$ and $b_i + b_j = T$ . RedDreamer has to paint each element of $a$ into one of two colors, white and black (for each element, the color is chosen independently), and then create two arrays $c$ and $d$ so that all white elements belong to $c$ , and all black elements belong to $d$ (it is possible that one of these two arrays becomes empty). RedDreamer wants to paint the elements in such a way that $f(c) + f(d)$ is minimum possible.

For example:

- if $n = 6$ , $T = 7$ and $a = [1, 2, 3, 4, 5, 6]$ , it is possible to paint the $1$ -st, the $4$ -th and the $5$ -th elements white, and all other elements black. So $c = [1, 4, 5]$ , $d = [2, 3, 6]$ , and $f(c) + f(d) = 0 + 0 = 0$ ;
- if $n = 3$ , $T = 6$ and $a = [3, 3, 3]$ , it is possible to paint the $1$ -st element white, and all other elements black. So $c = [3]$ , $d = [3, 3]$ , and $f(c) + f(d) = 0 + 1 = 1$ .

Help RedDreamer to paint the array optimally!

The first line contains one integer $t$ ( $1 \le t \le 1000$ ) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains two integers $n$ and $T$ ( $1 \le n \le 10^5$ , $0 \le T \le 10^9$ ) — the number of elements in the array and the unlucky integer, respectively.

The second line contains $n$ integers $a_1$ , $a_2$ , ..., $a_n$ ( $0 \le a_i \le 10^9$ ) — the elements of the array.

The sum of $n$ over all test cases does not exceed $10^5$ .

For each test case print $n$ integers: $p_1$ , $p_2$ , ..., $p_n$ (each $p_i$ is either $0$ or $1$ ) denoting the colors. If $p_i$ is $0$ , then $a_i$ is white and belongs to the array $c$ , otherwise it is black and belongs to the array $d$ .

If there are multiple answers that minimize the value of $f(c) + f(d)$ , print any of them.