1417_B. 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
```python
for I in range(int(input())):
    n,t = map(int,input().split())
    a = list(map(int,input().split()))
    d = []
    if t % 2 != 0:
        for i in range(n):
            if a[i] <= t // 2:
                d.append(1)
            else:
                d.append(0)
    else:
        p = 0
        for i in range(n):
            if a[i] < t//2:
                d.append(1)
            elif a[i] > t//2:
                d.append(0)
            else:
                d.append(p)
                p = (p + 1) % 2
    print(*d)
```