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!


-----Input-----

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$.


-----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

Difficulty: interview

Starter code:

Solutions:
T = int(input())
for test in range(T):
    n,t = list(map(int,input().split()))
    a = list(map(int,input().split()))
    res = []
    j=0
    for i in a:
        if(i*2<t):
            res+=["0"]
        elif(i*2>t):
            res+=["1"]
        else:
            res.append(["0","1"][j])
            j = 1-j
    print(" ".join(res))


t = int(input())
for _ in range(t):
    n, T = map(int, input().split())
    a = list(map(int, input().split()))
    white = set()
    if not T%2 and T//2 in a:
        halfcount = 0
        for i in range(len(a)):
            if a[i] == T//2:
                if halfcount % 2:
                    a[i] = 1
                else:
                    a[i] = 0
                halfcount += 1
            else:
                if T-a[i] in white:
                    a[i] = 1
                else:
                    white.add(a[i])
                    a[i] = 0
    else:
        for i in range(len(a)):
            if T-a[i] in white:
                a[i] = 1
            else:
                white.add(a[i])
                a[i] = 0
    print(*a)

import sys
import math
def II():
	return int(sys.stdin.readline())
 
def LI():
	return list(map(int, sys.stdin.readline().split()))
 
def MI():
	return list(map(int, sys.stdin.readline().split()))
 
def SI():
	return sys.stdin.readline().strip()
t = II()
for q in range(t):
    n,k = MI()
    a = LI()
    d = [0]*n
    c = a.count(k//2)
    boo = k%2 == 0
    count = 0
    for i in range(n):
        if a[i]<k//2:
            d[i] = 0
        elif a[i] == k//2:
            if not boo:
                d[i] = 0
            elif count<c//2:
                d[i] = 0
                count+=1
            else:
                d[i] = 1
        else:
            d[i] = 1
    print(*d)


from collections import defaultdict

T = int(input())

for t in range(T):
    n, T = [int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]

    pen_in_c = defaultdict(int)
    pen_in_d = defaultdict(int)

    answer = []
    for el in A:
        if pen_in_d[el] < pen_in_c[el]:
            answer.append(1)
            pen_in_d[T - el] += 1
        else:
            answer.append(0)
            pen_in_c[T - el] += 1

    print(' '.join(map(str, answer)))


t = int(input())
for _ in range(t):
    n,T = map(int,input().split())
    l1 = [int(x) for x in input().split()]
    current = 0
    for i in range(n):
        if T%2==0 and l1[i]==T//2:
            #print("HERE")
            if current:
                l1[i]=0
                current = 0
            else:
                l1[i]=1
                current = 1
        else:
            l1[i]=int(l1[i]>(T//2))
    print(*l1)

input=__import__('sys').stdin.readline
for _ in range(int(input())):
	n,T=map(int,input().split())
	s=list(map(int,input().split()))
	ans=[0]*n
	g={} # last ind with sum x
	for i in range(n):
		if T-s[i] in g:
			ans[i]=1-ans[g[T-s[i]]]
		g[s[i]]=i
	print(*ans)

for _ in range(int(input())):
    n, t = list(map(int, input().split()))
    *arr, = list(map(int, input().split()))
    flip = 0
    for i in range(n):
        if 2 * arr[i] > t:
            arr[i] = 1
        elif 2 * arr[i] < t:
            arr[i] = 0
        else:
            arr[i] = flip
            flip = 1 - flip
    print(*arr)





from collections import defaultdict


def solve():
    n, T = list(map(int, input().split()))
    a = list(map(int, input().split()))
    white = defaultdict(int)
    black = defaultdict(int)
    ans = [0]*n
    for i, x in enumerate(a):
        if white[T-x] > black[T-x]:
            black[x] += 1
            ans[i] = 1
        else:
            white[x] += 1
            ans[i] = 0
    print(*ans)
    return


def main():
    T = int(input())
    for i in range(T):
        solve()
    return


def __starting_point():
    main()


__starting_point()

t = int(input())

for case in range(t):
    n, T = map(int, input().split())
    a = [int(x) for x in input().split()]
    halfTticker = False
    halfT = T / 2
    white = set()

    for x in a:
        if x == halfT:
            print(int(halfTticker), end=' ')
            halfTticker = not halfTticker
        elif x in white:
            print(0, end=' ')
        elif T - x in white:
            print(1, end=' ')
        else:
            white.add(x)
            print(0, end=' ')

    print()



import sys
import math
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n,k = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    
    alt = 0
    ans = []
    for i in range(len(arr)):
        if k%2==1:
            if arr[i] < k/2:
                ans.append(0)
            else:
                ans.append(1)
        else:
            if arr[i] == k//2:
                ans.append(alt%2)
                alt += 1
            elif arr[i] < k//2:
                ans.append(0)
            else:
                ans.append(1)
                
    print(*ans)

import math
import sys
 
class Read:
    @staticmethod
    def string():
        return input()
 
    @staticmethod
    def int():
        return int(input())
 
    @staticmethod
    def list(sep=' '):
        return input().split(sep)
 
    @staticmethod
    def list_int(sep=' '):
        return list(map(int, input().split(sep)))
 

def solve():
    n, T = Read.list_int()
    a = Read.list_int()

    tmp = {}
    res = []
    for i in a:
        v = T - i
        r = '1'
        if v in tmp:
            if tmp[v] == '1':
                r = '0'
        tmp[i] = r
        res.append(r)

    print(' '.join(res))
    

# query_count = 1
query_count = Read.int()
while query_count:
    query_count -= 1
    solve()

for _ in range(int(input())):
    n, t = tuple(map(int, input().split()))
    arr = list(map(int, input().split()))

    ans = [-1] * n

    if t % 2 == 0:
        x = t // 2
        c = arr.count(x)

        c2 = 0
        for i in range(n):
            if arr[i] != x:
                continue
            if c2 < c // 2:
                ans[i] = 0
            else:
                ans[i] = 1
            c2 += 1

    for i in range(n):
        if ans[i] != -1:
            continue
        if arr[i] <= t // 2:
            ans[i] = 0
        else:
            ans[i] = 1

    print(*ans)


t = int(input())
for _ in range(t):
    n, u = map(int, input().split())
    a = list(map(int, input().split()))
    k=u//2
    p = [-1 for i in range(n)]
    if u%2!=0:
        for i in range(n):
            if a[i]<=k:
                p[i]=0
            else:
                p[i]=1
    else:
        x=0
        for i in range(n):
            if a[i]<k:
                p[i]=0
            elif a[i]>k:
                p[i]=1
            elif a[i]==k:
                if x==0:
                    p[i]=0
                    x=1
                else:
                    p[i]=1
                    x=0
    print(*p)

import os
from sys import stdin, stdout

class Input:
    def __init__(self):
        self.lines = stdin.readlines()
        self.idx = 0
    
    def line(self):
        try:
            return self.lines[self.idx].strip()
        finally:
            self.idx += 1
    
    def array(self, sep = ' ', cast = int):
        return list(map(cast, self.line().split(sep = sep)))
    
    def known_tests(self):
        num_of_cases, = self.array()
    
        for case in range(num_of_cases):
            yield self
    
    def unknown_tests(self):
        while self.idx < len(self.lines):
            yield self

def problem_solver():
    '''
    
    '''
    def solver(inpt):
        n, T = inpt.array()
        a = inpt.array()
        b = []
        c = 0

        for x in a:
            if x * 2 > T:
                b.append(1)
            elif x * 2 == T:
                b.append(c & 1)
                c += 1
            else:
                b.append(0)
        
        print(*b)

    '''Returns solver'''
    return solver

try:
    solver = problem_solver()
    for tc in Input().known_tests():
        solver(tc)
except Exception as e:
    import traceback
    traceback.print_exc(file=stdout)

import sys
input = sys.stdin.readline

def main():
    n, t = map(int, input().split())
    alst = list(map(int, input().split()))
    lst = [[i, a] for i, a in enumerate(alst)]
    lst.sort()
    if t % 2 == 0:
        mid = t // 2
    else:
        mid = t / 2
    ans = [-1 for _ in range(n)]
    flg = False
    for i, a in lst:
        if a < mid:
            ans[i] = 0
        elif a > mid:
            ans[i] = 1
        elif flg:
            flg = False
            ans[i] = 0
        else:
            flg = True
            ans[i] = 1
    print(*ans)
    
for _ in range(int(input())):
    main()

import os
import sys
import io

# input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline # 神奇快读，无法运行调试
GANS = []

# def print(*args): # 神奇快写，最后得写上os.write
#     nonlocal GANS
#     for i in args:
#         GANS.append(f'{i}'.encode())


t = int(input())

for _ in range(t):
    n,k = map(int,input().split())
    li = [int(i) for i in input().split()]
    d1 = {}
    d2 = {}
    col = []
    for i in li:
        if d1.get(k-i,0) > d2.get(k-i,0):
            d2[i] = d2.get(i,0) + 1
            col.append(1)
        else:
            d1[i] = d1.get(i,0) + 1
            col.append(0)
    print(*col)

import math
import collections
t=int(input())
for w in range(t):
    n,k=(int(i) for i in input().split())
    l=[int(i) for i in input().split()]
    l1=[0]*n
    c=0
    for i in range(n):
        if(l[i]>k/2):
            l1[i]=1
        elif(l[i]<k/2):
            l1[i]=0
        else:
            if(c%2==0):
                l1[i]=0
                c+=1
            else:
                l1[i]=1
                c+=1
    print(*l1)

for _ in range (int(input())):
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    s=set()
    c=0
    b=[0]*n
    for i in range (n):
        if 2*a[i]==k:
            b[i]=c
            c=1-c
        else:
            if a[i] in s:
                b[i]=1
            else:
                s.add(k-a[i])
    print(*b)

import random


def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)


def lcm(a, b):
    return (a * b) / gcd(a, b)


for _ in range(int(input())):
    #n = int(input())
    n,t= map(int, input().split())
    a = list(map(int, input().split()))
    d={}
    for i in range(n):
        if a[i] in d:
            d[a[i]].append(i)
        else:
            d[a[i]]=[i]
    ans=[-1]*n
    for i in d.keys():
        if ans[d[i][0]]==-1:
            if i==t//2:
                for j in range(len(d[i])//2):
                    ans[d[i][j]]=0
                for j in range(len(d[i])//2,len(d[i])):
                    ans[d[i][j]] = 1
            else:
                for j in range(len(d[i])):
                    ans[d[i][j]]=0
                if t-i in d:
                    for j in range(len(d[t-i])):
                        ans[d[t-i][j]]=1
    for i in ans:
        print(i,end=' ')
    print('')