#D2275. Two Arrays
Two Arrays
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 ≤ i < j ≤ 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!
Input
The first line contains one integer t (1 ≤ t ≤ 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 ≤ n ≤ 10^5, 0 ≤ T ≤ 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 ≤ a_i ≤ 10^9) — the elements of the array.
The sum of n over all test cases does not exceed 10^5.
Output
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.
Example
Input
2 6 7 1 2 3 4 5 6 3 6 3 3 3
Output
1 0 0 1 1 0 1 0 0
inputFormat
Input
The first line contains one integer t (1 ≤ t ≤ 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 ≤ n ≤ 10^5, 0 ≤ T ≤ 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 ≤ a_i ≤ 10^9) — the elements of the array.
The sum of n over all test cases does not exceed 10^5.
outputFormat
Output
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.
Example
Input
2 6 7 1 2 3 4 5 6 3 6 3 3 3
Output
1 0 0 1 1 0 1 0 0
样例
2
6 7
1 2 3 4 5 6
3 6
3 3 3
0 0 0 1 1 1
0 1 0