Mainak has two positive integers $n$ and $m$.

Mainak finds a sequence $a_1, a_2, \ldots, a_n$ of $n$ positive integers interesting, if for all integers $i$ ($1 \le i \le n$), the bitwise XOR of all elements in $a$ which are strictly less than $a_i$ is $0$. Formally if $p_i$ is the bitwise XOR of all elements in $a$ which are strictly less than $a_i$, then $a$ is an interesting sequence if $p_1 = p_2 = \ldots = p_n = 0$.

For example, sequences $[1,3,2,3,1,2,3]$, $[4,4,4,4]$, $[25]$ are interesting, whereas $[1,2,3,4]$ ($p_2 = 1 \ne 0$), $[4,1,1,2,4]$ ($p_1 = 1 \oplus 1 \oplus 2 = 2 \ne 0$), $[29,30,30]$ ($p_2 = 29 \ne 0$) aren't interesting.

Here $a \oplus b$ denotes bitwise XOR of integers $a$ and $b$.

Find any interesting sequence $a_1, a_2, \ldots, a_n$ (or report that there exists no such sequence) such that the sum of the elements in the sequence $a$ is equal to $m$, i.e. $a_1 + a_2 \ldots + a_n = m$.

As a reminder, the bitwise XOR of an empty sequence is considered to be $0$.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Description of the test cases follows.

The first line and the only line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le 10^9$) — the length of the sequence and the sum of the elements.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, if there exists some interesting sequence, output "Yes" on the first line, otherwise output "No". You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

If the answer is "Yes", output $n$ positive integers $a_1, a_2, \ldots, a_n$ ($a_i \ge 1$), forming an interesting sequence such that $a_1 + a_2 \ldots + a_n = m$. If there are multiple solutions, output any.


-----Examples-----

Input
4
1 3
6 12
2 1
3 6
Output
Yes
3
Yes
1 3 2 2 3 1
No
Yes
2 2 2


-----Note-----

In the first test case, $[3]$ is the only interesting sequence of length $1$ having sum $3$.

In the third test case, there is no sequence of length $2$ having sum of elements equal to $1$, so there is no such interesting sequence.

In the fourth test case, $p_1 = p_2 = p_3 = 0$, because bitwise XOR of an empty sequence is $0$.

Source: codeforces | Difficulty: EASY
Tags: Bit manipulation

Mathematics

Constructive algorithms


Solutions:
import sys
print = sys.stdout.write
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n > m:
		print('NO\n')
		continue
	if n % 2 == 1:
		print('YES\n')
		print('1 ' * (n - 1))
		print(f'{m - (n - 1)}\n')
	elif m % 2 == 0:
		print('YES\n')
		print('1 ' * (n - 2))
		print(f'{(m - (n - 2)) // 2} {(m - (n - 2)) // 2}\n')
	else:
		print('NO\n')


output = ''
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m < n:
		output += 'NO\n'
	elif m == n:
		output += 'YES\n' + '1 ' * n
	elif n % 2 == 1:
		output += 'YES\n' + f'{m - n + 1} ' + '1 ' * (n - 1)
	elif m % 2 == 0:
		output += 'YES\n' + f'{(m - n + 2) // 2} ' * 2 + '1 ' * (n - 2)
	else:
		output += 'NO\n'
	output += '\n'
print(output)


import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	if n == 1:
		print('YES')
		ans = [m]
		print(*ans)
		return
	if m < n:
		print('NO')
	elif m == n:
		print('YES')
		ans = [1] * n
		print(*ans)
	elif (n - 1) % 2 == 0:
		print('YES')
		ans = [m - n + 1] + [1] * (n - 1)
		print(*ans)
	elif m % 2 == 0:
		print('YES')
		ans = [(m - n + 2) // 2, (m - n + 2) // 2] + [1] * (n - 2)
		print(*ans)
	else:
		print('NO')
	return
for _ in range(int(input())):
	solve()


s = ''
for _ in range(int(input())):
	(n, sm) = map(int, input().split())
	if n > sm:
		s += 'NO\n'
	elif n == sm:
		s += 'YES\n' + ' ' + '1 ' * n + '\n'
	elif n % 2 == 1:
		s += 'YES\n' + str(sm - (n - 1)) + ' ' + '1 ' * (n - 1) + '\n'
	elif sm % 2 == 0:
		s += 'YES\n' + str((sm - (n - 2)) // 2) + ' ' + str((sm - (n - 2)) // 2) + ' ' + '1 ' * (n - 2) + '\n'
	else:
		s += 'NO\n'
print(s)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n > m or (n % 2 == 0 and m % 2 == 1):
		print('NO')
	else:
		print('YES')
		l = []
		if n % 2 == 1:
			print('1 ' * (n - 1) + str(m - n + 1))
		else:
			print('1 ' * (n - 2) + (str((m - (n - 2)) // 2) + ' ') * 2)


import sys
input = sys.stdin.readline
for i in range(int(input())):
	(n, m) = map(int, input().split())
	if n > m:
		print('NO')
		continue
	if n % 2 == 1:
		print('YES')
		for i in range(n - 1):
			print(1, end=' ')
		print(m - n + 1)
	elif m % 2 == 0:
		print('YES')
		for i in range(n - 2):
			print(1, end=' ')
		print((m - n + 2) // 2, (m - n + 2) // 2)
	else:
		print('NO')


output = ''
for caseno in range(int(input())):
	(n, m) = map(int, input().split())
	if n > m:
		output += 'NO\n'
	elif m == n:
		output += 'YES\n'
		output += '1 ' * n
	elif n % 2 == 1:
		output += 'YES\n'
		output += '1 ' * (n - 1)
		left_m = m - (n - 1)
		half_left_m = int(left_m)
		output += str(half_left_m) + ' '
	elif m % 2 == 0:
		output += 'YES\n'
		output += '1 ' * (n - 2)
		left_m = m - (n - 2)
		half_left_m = int(left_m // 2)
		output += (str(half_left_m) + ' ') * 2
	else:
		output += 'NO\n'
	output += '\n'
print(output)


import sys
input = sys.stdin.readline

def int_num():
	return int(input())

def int_list():
	return list(map(int, input().split()))

def str_list():
	s = input()
	return list(s[:len(s) - 1])

def instr():
	return input().strip()

def invr():
	return map(int, input().split())

def solve():
	(n, k) = int_list()
	if n > k:
		print('NO')
		return
	if n % 2 == 0 and k % 2 == 1:
		print('NO')
		return
	print('YES')
	if n % 2 == 1:
		a = [1] * (n - 1)
		a.append(k + 1 - n)
	else:
		a = [1] * (n - 2)
		a.append((k + 2 - n) // 2)
		a.append((k + 2 - n) // 2)
	print(*a)

def main():
	t = int_num()
	while t:
		solve()
		t -= 1
	return
main()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	if n > m or (n % 2 == 0 and m % 2 == 1):
		print('NO')
	else:
		print('YES')
		ans = []
		if n % 2 == 1:
			ans.extend([1] * (n - 1) + [m - n + 1])
		else:
			ans.extend([1] * (n - 2) + [(m - n + 2) // 2] * 2)
		print(*ans, sep=' ')


import sys
import math
from collections import Counter
from collections import defaultdict

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def solve(length, summ):
	if summ < length:
		return ['NO']
	if length == summ:
		ans = [1] * length
		print('YES')
		return ans
	if length % 2 == 0 and summ % 2 != 0:
		return ['NO']
	if length % 2 != 0:
		ans = []
		for i in range(length - 1):
			ans.append(1)
		ans.append(summ - (length - 1))
		print('YES')
		return ans
	if length % 2 == 0 and summ % 2 == 0:
		ans = []
		for i in range(length - 2):
			ans.append(1)
		rem = summ - (length - 2)
		ans.append(rem // 2)
		ans.append(rem // 2)
		print('YES')
		return ans
t = int(input())
for _ in range(t):
	arr = get_ints()
	print(*solve(arr[0], arr[1]))


import sys
input = sys.stdin.readline
in_il = lambda : list(map(int, input().split()))
in_sl = lambda : input().split()
in_i = lambda : int(input())
MAX_INT = float('inf')

def solve():
	(n, m) = in_il()
	if n > m:
		print('NO')
	elif n % 2 != 0:
		print('YES')
		for i in range(n - 1):
			print(1, end=' ')
		print(m - n + 1)
	elif n % 2 == 0 and m % 2 == 0:
		print('YES')
		for i in range(n - 2):
			print(1, end=' ')
		print((m - n + 2) // 2, (m - n + 2) // 2)
	else:
		print('NO')
for _ in range(in_i()):
	solve()


import math
import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split(' '))
	lst = []
	if m < n:
		print('NO')
		return
	if n == 1:
		lst = [m]
	elif n == 2:
		if m % 2:
			print('NO')
			return
		lst = [m // 2, m // 2]
	elif n % 2:
		for i in range(n - 1):
			lst.append(1)
		lst.append(m - (n - 1))
	else:
		for i in range(n - 2):
			lst.append(1)
		b = m - (n - 2)
		if b % 2:
			print('NO')
			return
		lst.append(b // 2)
		lst.append(b // 2)
	print('YES')
	for i in lst:
		print(i, end=' ')
	print()
t = int(input())
while t:
	t -= 1
	solve()


import itertools
import sys
import math
from bisect import *
from collections import deque
input = sys.stdin.readline
from collections import defaultdict
from collections import Counter
for i in range(int(input())):
	(n, m) = map(int, input().split())
	if m < n:
		print('NO')
		continue
	elif n & 1:
		print('YES')
		for i in range(1, n):
			print(1, end=' ')
			m -= 1
		print(m, end='')
		print('')
	elif m & 1:
		print('NO')
	else:
		print('YES')
		for i in range(2, n):
			print(1, end=' ')
			m -= 1
		print(m // 2, end=' ')
		print(m // 2, end=' ')
		print()


import sys

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def fun(a, b):
	x = []
	if b // a == 0:
		return 'No'
	if a == b:
		return [1] * a
	if a % 2 == 0 and b % 2 != 0:
		return 'No'
	if a % 2 != 0 and b % 2 != 0:
		for i in range(a - 1):
			x.append(1)
		x.append(b - (a - 1))
		return x
	if a % 2 == 0 and b % 2 == 0:
		for i in range(a - 2):
			x.append(1)
		x.append((b - (a - 2)) // 2)
		x.append((b - (a - 2)) // 2)
		return x
	else:
		for i in range(a - 1):
			x.append(1)
		x.append(b - (a - 1))
		return x
l = int(input())
for _ in range(l):
	arr = get_ints()
	a = int(arr[0])
	b = int(arr[-1])
	z = fun(a, b)
	if z != 'No':
		print('YES')
		print(*z)
	else:
		print('NO')


def solve():
	(n, m) = map(int, input().split())
	if n == 1:
		print('YES')
		print(m)
	elif n == m:
		print('YES')
		print('1 ' * n)
	elif m < n:
		print('NO')
	elif n % 2 == 1:
		print('YES')
		print('1 ' * (n - 1), end='')
		print(m - n + 1)
	elif n % 2 == 0 and m % 2 == 0:
		print('YES')
		print('1 ' * (n - 2), end='')
		print((m - n + 2) // 2, end=' ')
		print((m - n + 2) // 2)
	else:
		print('NO')
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	bl = True
	if n > m:
		print('NO')
		bl = False
	if bl:
		if n % 2 == 0:
			if m % 2 != 0:
				bl = False
				print('NO')
	if bl:
		if n == 1:
			print('YES')
			print(m)
			bl = False
	if bl:
		if n % 2 == 1:
			print('YES')
			print((n - 1) * '1 ', end='')
			print(m - n + 1)
		else:
			print('YES')
			print((n - 2) * '1 ', end='')
			print((m - n + 2) // 2, (m - n + 2) // 2)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	if n > m or (n % 2 == 0 and m % 2 != 0):
		print('NO')
	else:
		print('YES')
		if n == 1:
			print(m)
		else:
			res = []
			if n % 2:
				res += ['1'] * (n - 1) + [str(m - n + 1)]
			else:
				res += ['1'] * (n - 2) + [str((m - n + 2) // 2)] * 2
			print(' '.join(res))


from math import factorial as fact, comb as ncr
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as cnt
lin = lambda : list(map(int, input().split()))
nin = lambda : int(input())
sin = lambda : str(input())
bi = lambda n: bin(n).replace('0b', '')
yes = lambda : print('YES')
no = lambda : print('NO')

def kyutlederahaibhai():
	(n, s) = map(int, input().split())
	if n > s:
		no()
		return
	if n == 1:
		yes()
		print(s)
		return
	if n % 2 == 0 and s % 2:
		no()
		return
	yes()
	if n % 2:
		for i in range(n - 1):
			print(1, end=' ')
		s -= n - 1
		print(s)
	else:
		for i in range(n - 2):
			print(1, end=' ')
		s -= n - 2
		print(s // 2, end=' ')
		print(s // 2)
for pratyush in range(int(input())):
	kyutlederahaibhai()


n = int(input())
for p in range(0, n):
	(n, m) = map(int, input().split())
	if n > m:
		print('NO')
	elif n % 2 == 1:
		print('YES')
		if n != 1:
			for i in range(0, n - 1):
				print(1, end=' ')
			print(m - n + 1)
		else:
			print(m)
	elif m % 2 != 0:
		print('NO')
	else:
		print('YES')
		for i in range(0, n - 2):
			print(1, end=' ')
		print((m - n + 2) // 2, (m - n + 2) // 2)


def solve():
	(n, s) = list(map(int, input().split()))
	if n > s:
		print('NO')
		return
	if n == 1:
		print('YES')
		print(s)
		return
	if n % 2 == 0 and s % 2:
		print('NO')
		return
	l = []
	print('YES')
	if n % 2 == 0:
		for i in range(n - 2):
			l.append(1)
		s -= n - 2
		l.append(s // 2)
		l.append(s // 2)
		print(*l)
	else:
		for i in range(n - 1):
			l.append(1)
		s -= n - 1
		l.append(s)
		print(*l)
for pratyush in range(int(input())):
	solve()


for jj in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	if n > m:
		print('NO')
	elif n == 1:
		print('YES')
		print(*[m])
	elif n == m:
		print('YES')
		t = [1] * n
		print(*t)
	elif n % 2 == 1:
		print('YES')
		t = [1] * (n - 1) + [m - n + 1]
		print(*t)
	elif m % 2 == 1:
		print('NO')
	else:
		print('YES')
		t = [1] * (n - 2) + [(m - n + 2) // 2] * 2
		print(*t)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n > m or (not n & 1 and m & 1):
		print('NO')
		continue
	print('YES')
	if n > 1:
		for i in range(n - 2):
			print(1, end=' ')
		if n == m:
			print('1 1')
		elif n & 1:
			print('1 {}'.format(m - n + 1))
		else:
			g = (m - n + 2) // 2
			print('{} {}'.format(g, g))
	else:
		print(m)