Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef is baking a large cake! The cake consists of $N$ different ingredients numbered $1$ through $N$. Chef can choose how much of each ingredient to use in his cake recipe; let's denote the amount of the $i$-th ingredient used in the cake by $g_{i}$. Chef can only measure ingredients in fixed whole units, so the amounts of all ingredients must be integers.

In order to keep the cake inexpensive (and, of course, use each ingredient from the recipe), the chosen amounts of ingredients have to satisfy the condition $1 ≤ g_{i} ≤ K$ (for each $1 ≤ i ≤ N$). The *taste* of the resulting cake is computed as the bitwise XOR of the amounts of all ingredients, i.e. $g_{1} \oplus g_{2} \oplus \dots \oplus g_{N}$. For example, if $N=3$ and $g = [1, 2, 5]$, the taste of the cake is equal to $1 \oplus 2 \oplus 5 = 6$.

Please help Chef and find one way to choose the amounts of all ingredients such that the taste of the cake is maximum possible.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains two space-separated integers $N$ and $K$. 

------  Output ------
For each test case, print a single line containing $N$ space-separated integers $g_{1}, g_{2}, \dots, g_{N}$ — the amounts of ingredients $1, 2, \dots, N$.

------  Constraints  ------
$1 ≤ T ≤ 40$
$1 ≤ N ≤ 10^{4}$
$1 ≤ K ≤ 10^{9}$

----- Sample Input 1 ------ 
2
3 5
4 3
----- Sample Output 1 ------ 
5 1 3
1 2 3 3
----- explanation 1 ------ 
Example case 1: The maximum possible taste of the cake is $5 \oplus 1 \oplus 3 = 7$.

Example case 2: The maximum possible taste is $1 \oplus 2 \oplus 3 \oplus 3 = 3$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics

Constructive algorithms


Solutions:
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ans = []
	if n % 2 == 0:
		bo = ''
		c = bin(k)[2:]
		for i in c:
			if i == '0':
				bo += '1'
			else:
				bo += '0'
		d = int(bo, 2)
		for i in range(n - 2):
			ans.append(k)
		if d == 0:
			k1 = '1' + '0' * (len(c) - 1)
			k2 = '0' + '1' * (len(c) - 1)
			ans.append(int(k1, 2))
			ans.append(int(k2, 2))
		else:
			ans.append(d)
			ans.append(k)
	else:
		bo = ''
		c = bin(k)[2:]
		for i in c:
			if i == '0':
				bo += '1'
			else:
				bo += '0'
		d = int(bo, 2)
		if d == 0:
			ans.append(k)
			ans.append(k)
			ans.append(k)
		else:
			fa = ''
			for i in range(1, len(c)):
				if c[i] == '1':
					fa += '1'
				else:
					fa += '0'
			k2 = '0' + '1' * (len(c) - 1)
			ans.append(k)
			if int(fa, 2) != 0:
				ans.append(int(fa, 2))
				ans.append(int(k2, 2))
			else:
				k2 = '0' + '1' * (len(c) - 2) + '0'
				ans.append(int(k2, 2))
				ans.append(1)
		for i in range(n - 3):
			ans.append(k)
	if n == 1:
		ans = [k]
	elif n % 2 != 0 and k == 2:
		ans = [k] * n
	elif n % 2 == 0 and k == 1:
		ans = [1] * n
	print(*ans)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if n == 1:
		print(k)
		continue
	if k == 1:
		ans = [1] * n
		print(*ans)
		continue
	if k == 2:
		if n & 1:
			ans = [2]
			for i in range(n - 1):
				ans.append(1)
			print(*ans)
			continue
		ans = [2]
		for i in range(n - 1):
			ans.append(1)
		print(*ans)
		continue
	st = list('{0:b}'.format(k))
	w = len(st)
	s = []
	for i in range(w):
		if st[i] == '0':
			s.append('1')
		else:
			s.append('0')
	if s.count('1') == 0:
		if n & 1:
			v = [k] * n
			print(*v)
			continue
		s1 = '1' + '0' * (w - 1)
		s2 = '1' * (w - 1)
		s1 = int(s1, 2)
		s2 = int(s2, 2)
		v = [k] * (n - 2)
		v.append(s1)
		v.append(s2)
		print(*v)
		continue
	for i in range(w):
		if s[i] == '1':
			break
	s = ''.join((str(e) for e in s))
	s = s[i:]
	s1 = '1' + '0' * (w - i - 1)
	if s1 == s:
		s1 = '1' + '1' + '0' * (w - i - 2)
	s2 = ''
	for i in range(len(s1)):
		if s[i] == '1':
			if s1[i] == '1':
				s2 += '0'
			else:
				s2 += '1'
		elif s1[i] == '1':
			s2 += '1'
		else:
			s2 += '0'
	s = int(s, 2)
	s1 = int(s1, 2)
	s2 = int(s2, 2)
	if n & 1:
		ans = [k] * (n - 2)
		ans.append(s1)
		ans.append(s2)
		print(*ans)
		continue
	ans = [k] * (n - 1)
	ans.append(s)
	print(*ans)


t = int(input())
for ijk in range(0, t):
	(n, k) = map(int, input().strip().split())
	bit = []
	req = []
	c = 0
	length = 0
	f = int(k)
	while k != 0:
		w = k % 2
		length += 1
		bit.append(w)
		k = k // 2
		if w == 0:
			c += 1
			req.append(1)
		else:
			req.append(0)
	if c == 0:
		if f > 1:
			if n % 2 == 0:
				if n == 2:
					print(f - 1, 1)
				else:
					print(f, 1, 2, 3, '1 ' * (n - 4))
			else:
				print(f, '1 ' * (n - 1))
		else:
			print('1 ' * n)
	elif n % 2 == 0:
		num = 0
		for i in range(0, length):
			if bit[i] == 0:
				num += pow(2, i)
		print(f, num, '1 ' * (n - 2))
	elif n == 1:
		print(f)
	elif c == 1:
		if f == 2:
			print(f, '1 ' * (n - 1))
		else:
			n1 = n2 = 0
			for i in range(0, length):
				if bit[i] == 0:
					n1 += pow(2, i)
					break
			if i == 0:
				n2 += pow(2, i + 1)
				n1 += pow(2, i + 1)
			else:
				n2 += pow(2, i - 1)
				n1 += pow(2, i - 1)
			print(n1, n2, f, (n - 3) * '1 ')
	else:
		y = 0
		n1 = n2 = 0
		for i in range(0, length):
			if bit[i] == 0:
				if y == 0:
					n1 += pow(2, i)
					y = 1
				else:
					n2 += pow(2, i)
					y = 0
		print(f, n1, n2, '1 ' * (n - 3))


import sys
t = int(input())
for _ in range(t):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	i = 0
	while 2 ** i <= k:
		i += 1
	ka = 2 ** i - 1
	if k == 1:
		for _ in range(n):
			print(k, end=' ')
		print()
		continue
	elif k == 2 and n % 2 != 0:
		for _ in range(n):
			print(k, end=' ')
		print()
		continue
	if n % 2 == 0:
		i = i - 1
		a1 = 2 ** i
		a2 = a1 - 1
		print(a2, end=' ')
		print(a1, end=' ')
		for _ in range(n - 2):
			print(k, end=' ')
	elif n == 1:
		print(k, end='')
	else:
		i = i - 1
		a1 = 2 ** i
		if k == a1:
			print(k, 1, k - 2, end=' ')
			for _ in range(n - 3):
				print(k, end=' ')
		else:
			print(a1 + 1, 1, a1 - 1, end=' ')
			for _ in range(n - 3):
				print(k, end=' ')
	print()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 1:
		print(k)
	elif k == 1:
		for _ in range(n):
			print(1, end=' ')
		print()
	elif n % 2 != 0 and k == 2:
		for _ in range(n - 1):
			print(1, end=' ')
		print(2)
	else:
		ans = 1
		while ans <= k:
			ans *= 2
		ans -= 1
		if k != ans:
			if n % 2 == 0:
				b = k ^ ans
				print(k, b, end=' ')
				for _ in range(n - 2):
					print(1, end=' ')
				print()
			else:
				b = k ^ ans ^ 1
				if b != 0:
					print(k, b, 1, end=' ')
					for _ in range(n - 3):
						print(1, end=' ')
					print()
				else:
					b = k ^ ans ^ 2
					print(k, b, 2, end=' ')
					for _ in range(n - 3):
						print(1, end=' ')
					print()
		elif n % 2 != 0:
			print(k, end=' ')
			for _ in range(n - 1):
				print(1, end=' ')
			print()
		elif n == 2:
			print(k - 1, 1)
		elif n >= 4:
			print(k, 1, 2, 3, end=' ')
			for _ in range(n - 4):
				print(1, end=' ')
			print()