B. Two Arrays
greedy; math; sortings
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.