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

You are given two integers x and N. Consider all integers between 1 and N inclusive, except x. We want to partition these integers into two disjoint sets (each integer has to appear in exactly one set) such that the sums of numbers in these sets are equal.
Find one valid partition or determine that it doesn't exist.

------ 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 x and N.

------ Output ------ 

For each test case:
If there's no way to partition the numbers into two sets with equal sums, print a single line containing the string "impossible" (without quotes).
Otherwise, print a single line containing a string with length N.
The x-th character of this string should be '2'.
For each valid i ≠ x, the i-th character of this string should be '0' if number i should be in the first set or '1' if it should be in the second set.

------ Constraints ------ 

$1 ≤ T ≤ 10,000$
$2 ≤ N ≤ 1,000,000$
$1 ≤ x ≤ N $
$1 ≤ sum of N in all test cases ≤ 1,000,000$

------ Subtasks ------ 

Subtask #1 (20 points): sum of N in all test cases ≤ 50

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
3
2 4
5 5
1 2
----- Sample Output 1 ------ 
0201
01102
impossible

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(x, n) = map(int, input().split())
	if n < 4 or (n ^ n >> 1 ^ x) & 1:
		print('impossible')
	elif x == n == 5:
		print('01102')
	else:
		r = ['0'] * n
		r[x - 1] = '2'
		s = (n * (n + 1) // 2 - x) // 2
		while s > n:
			if x != n != s - x:
				r[n - 1] = '1'
				s -= n
			n -= 1
		r[s - 1] = '1'
		print(''.join(r))


table = []

def init_table(rows, cols, x):
	global table
	table = [[True] * cols]
	table.extend([[False] * cols for _ in range(rows - 1)])
	partition(rows, cols, x, rows, cols)

def update_table(rows, cols, x):
	global table
	prev_cols = len(table[0])
	prev_rows = len(table)
	col_diff = cols - prev_cols
	row_diff = rows - prev_rows
	if col_diff > 0:
		table[0].extend(col_diff * [True])
		for i in range(1, prev_rows):
			for j in range(prev_cols, cols):
				difference = i - j
				if difference < 0 or j == x:
					table[i].append(table[i][j - 1])
				else:
					table[i].append(table[i][j - 1] or table[difference][j - 1])
		table.extend([[False] * cols for _ in range(row_diff)])
		partition(rows, cols, x, prev_rows, cols, 1, prev_cols)
		partition(rows, cols, x, rows, cols, prev_rows, 1)
	if x >= prev_cols:
		exclude_x(x, rows, cols)

def partition(rows, cols, x, row_end, col_end, row_start=1, col_start=1):
	global table
	for i in range(row_start, row_end):
		for j in range(col_start, col_end):
			difference = i - j
			if difference < 0 or j == x:
				table[i][j] = table[i][j - 1]
			else:
				table[i][j] = table[i][j - 1] or table[difference][j - 1]

def reinclude_x(x, rows, cols):
	partition(rows, cols, 0, rows, cols, x, x)

def exclude_x(x, rows, cols):
	partition(rows, cols, x, rows, cols, x, x)

def prtition(x, N):
	global table
	total = N * (N + 1) // 2 - x
	if total % 2 != 0:
		return False
	half_total = total // 2
	rows = half_total + 1
	cols = N + 1
	if not table:
		init_table(rows, cols, x)
	else:
		update_table(rows, cols, x)
	half_set = set()
	if table[half_total][N]:
		while half_total > 0 and N > 0:
			difference = half_total - N
			if N != x and difference >= 0 and table[difference][N - 1]:
				half_set.add(N)
				half_total = difference
			N -= 1
	reinclude_x(x, rows, cols)
	return half_set

def natural(x, N):
	if N <= 3:
		return False
	pair = N + 1
	pretotal = N * pair // 2
	total = pretotal - x
	if total % 2 != 0:
		return False
	set_pair = pair if N % 2 == 0 else N
	half_set = set()
	quarter_N = N // 4
	if pretotal % 2 == 0:
		if N % 2 != 0:
			quarter_N += 1
		half_x = x // 2
		x_complement = set_pair - x
		half_set.add(x_complement)
		if x_complement == half_x:
			half_set.add(1)
			half_set.add(half_x - 1)
		else:
			half_set.add(half_x)
		pairs = 1
	else:
		x_complement = set_pair - x
		half_x_complement = x_complement // 2
		half_set.add(x_complement)
		half_x_complement_complement = set_pair - half_x_complement
		if x_complement == half_x_complement_complement:
			half_set.add(1)
			half_set.add(half_x_complement_complement - 1)
		else:
			half_set.add(set_pair - half_x_complement)
		pairs = 0 if x_complement == 0 else 1
	i = 1 if N % 2 == 0 else 0
	while pairs < quarter_N and i <= N // 2:
		complement = set_pair - i
		if i not in half_set and complement not in half_set:
			half_set.add(i)
			half_set.add(complement)
			pairs += 1
		i += 1
	if i > N // 2 and pairs < quarter_N:
		return False
	return half_set

def output(i, x, half_set, N):
	print(0 if i in half_set else 1, end='' if i < N else None)
T = int(input())
for _ in range(T):
	(x, N) = list(map(int, input().split()))
	half_set = natural(x, N)
	if half_set:
		for i in range(1, x):
			output(i, x, half_set, N)
		print(2, end='' if x < N else None)
		for i in range(x + 1, N + 1):
			output(i, x, half_set, N)
	else:
		print('impossible')


def sumAll(n):
	return n * (n + 1) / 2

def partition(arr, x, sumSet):
	array = list(arr)
	n = len(array)
	i = n - 1
	while sumSet >= 0:
		if x != i:
			if sumSet >= i:
				array[i - 1] = 1
				sumSet -= i
			if sumSet == 0:
				break
		i -= 1
	return array
try:
	t = int(input())
except EOFError:
	pass
while t:
	(x, n) = input().split(' ')
	(x, n) = (int(x), int(n))
	arr = [int(0) for _ in range(n)]
	arr[x - 1] = 2
	tup = tuple(arr)
	temp = sumAll(n) - x
	if temp % 2 != 0 or n <= 3:
		print('impossible')
	else:
		setSum = temp / 2
		a = setSum
		i = n
		while a >= 0:
			if x != i:
				if a == x:
					arr = partition(tup, x, setSum)
					break
				if a >= i:
					arr[i - 1] = 1
					a -= i
				if a == 0:
					break
			i -= 1
		if arr[0] != 2:
			temps = arr[0]
		else:
			temps = arr[1]
		for i in range(n):
			if arr[i] == temps:
				print('0', end='')
			elif arr[i] == 2:
				print('2', end='')
			else:
				print('1', end='')
	print()
	t -= 1


for nitish in range(int(input())):
	(x, n) = list(map(int, input().strip().split(' ')))
	totsum = n * (n + 1) // 2 - x
	sum0 = totsum
	if n <= 3 or totsum % 2 != 0:
		print('impossible')
		continue
	sum1 = 0
	a = [0 for i in range(n + 1)]
	for i in range(1, n + 1):
		if i != x and sum0 - sum1 > 2 * i:
			a[i] = 1
			sum1 += i
			sum0 -= i
			s = i
		elif i == x:
			a[i] = 2
		else:
			a[i] = 0
	t = (sum0 - sum1) // 2
	if t == 1 and a[s + 1] == 2:
		a[1] = 0
		a[s] = 0
		a[s + 2] = 1
		for ii in range(1, n + 1):
			print(a[ii], end='')
		print()
		continue
	for i in range(s + 1, n + 1):
		if a[i] == 0 and a[i - t] == 1:
			a[i] += 1
			a[i - t] -= 1
			break
	for ii in range(1, n + 1):
		print(a[ii], end='')
	print()


import numpy as np
import math as math

def solve(j, a, b, ad, bd):
	flag = 0
	if sum(a) < sum(b):
		for i in a:
			if bd.get(i + j, 0):
				b.append(i)
				b.remove(i + j)
				bd[i] = 1
				bd[i + j] = 0
				a.append(i + j)
				a.remove(i)
				ad[i + j] = 1
				ad[i] = 0
				flag = 1
				break
	if sum(b) < sum(a) and (not flag):
		for i in b:
			if ad.get(i + j, 0):
				b.append(i + j)
				b.remove(i)
				a.append(i)
				a.remove(i + j)
				bd[i + j] = 1
				bd[i] = 0
				ad[i] = 1
				ad[i + j] = 0
				flag = 1
				break
t = int(input())
totaln = 0
for b in range(t):
	(x, n) = [int(i) for i in input().split(' ')]
	a = []
	b = []
	ad = {}
	bd = {}
	flag = 0
	sum1 = 0
	for i in range(1, n + 1):
		if i != x:
			sum1 += i
			if flag:
				a.append(i)
				ad[i] = 1
				flag = 0
			else:
				b.append(i)
				bd[i] = 1
				flag = 1
	if sum1 % 2 or (n == 1 and n == x) or n <= 3:
		print('impossible')
		continue
	a.insert(0, 0)
	b.insert(0, 0)
	flag = 0
	j = math.fabs(sum(a) - sum(b)) / 2
	if (sum(a) - sum(b)) % 2:
		print('impossible')
		continue
	solve(j, a, b, ad, bd)
	f = math.ceil(j / 2)
	g = math.floor(j / 2)
	while sum(a) != sum(b):
		solve(f, a, b, ad, bd)
		solve(g, a, b, ad, bd)
		f += 1
		g -= 1
	ans = [i for i in range(0, n + 1)]
	for i in a:
		ans[int(i)] = 0
	for i in b:
		ans[int(i)] = 1
	for i in range(1, n + 1):
		if i != x:
			print(ans[i], end='')
		else:
			print(2, end='')
	print()


import itertools as I
t = int(input())
for _ in range(t):
	(x, n) = map(int, input().split())
	A = []
	a = 0
	b = 0
	brute = min(n, 6)
	for i in reversed(range(brute, n + 1)):
		if i != x:
			if a < b:
				a += i
				A.append(0)
			else:
				b += i
				A.append(1)
		else:
			A.append(2)
	oa = a
	ob = b
	togo = list(range(1, brute))
	if x in togo:
		togo.remove(x)
	done = False
	for p in I.permutations(togo):
		for i in range(1, len(p) + 1):
			a = oa
			b = ob
			AA = p[:i]
			BB = p[i:]
			a += sum(AA)
			b += sum(BB)
			if a == b:
				for i in reversed(range(1, brute)):
					if i == x:
						A.append(2)
					elif i in AA:
						A.append(0)
					else:
						A.append(1)
				done = True
				break
		if done:
			break
	if done:
		print(''.join((str(a) for a in reversed(A))))
	else:
		print('impossible')