Chef built a binary string S that has exactly N hills and M valleys.

A hill is any index 1 < i < |S| such that both its neighbors are strictly smaller than it, i.e, S_{i-1} < S_{i} and S_{i+1} < S_{i}.

A valley is any index 1 < i < |S| such that both its neighbors are strictly larger than it, i.e, S_{i-1} > S_{i} and S_{i+1} > S_{i}.

Chef thinks that his string S is the shortest among all binary strings with N hills and M valleys.  You don't quite trust his words, so to verify his claim you would like to find the shortest binary string with exactly N hills and M valleys.

If there are multiple possible binary strings of the least length satisfying the given condition, you may print any of them.

------ Input Format ------ 

- The first line of input will contain 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 M, the required number of hills and valleys respectively.

------ Output Format ------ 

For each test case, output two lines.
- The first line contains the length of the binary string you constructed to satisfy the given conditions.
- The second line contains the string itself.

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

$1 ≤ T ≤ 2500$
$1 ≤ N ≤ 500$
$1 ≤ M ≤ 500$
- The sum of lengths of the answer strings across all test cases does not exceed $2\cdot 10^{5}$

------ subtasks ------ 

Subtask 1 (10 points): 
$1 ≤ N ≤ 50$
$1 ≤ M ≤ 50$
You may output any string of length not exceeding $320$ containing exactly $N$ hills and $M$ valleys:  it need not be shortest by length. It is guaranteed that at least one such string with length $≤ 320$ exists.

Subtask 2 (90 points):
Original constraints
The binary string you construct must be shortest by length.

----- Sample Input 1 ------ 
3
3 2
2 3
3 3
----- Sample Output 1 ------ 
7
0101010
7
1010101
8
01010101
----- explanation 1 ------ 
Test case $1$: The given string has hills at indices $2, 4, 6$ and valleys at indices $3, 5$. It can be verified that there is no string of length $6$ or less with $3$ hills and $2$ valleys.  Note that for subtask $1$, a binary string like $001010100$ will also be accepted as a valid output, even though it is not shortest by length. 

Test case $3$: Apart from the given string, another possible string of length $8$ that has $3$ hills and $3$ valleys is $10101010$. You may print any of them.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc


Solutions:
def soln(n: int, m: int) -> int:
	if n >= m:
		great = '1'
		less = '0'
	else:
		great = '0'
		less = '1'
	s = less
	for i in range(min(n, m)):
		s += great + less
	if n == m:
		s += great
		print(len(s))
		print(s)
		return
	for i in range(abs(n - m)):
		s += great + less * 2
	print(len(s) - 1)
	print(s[:len(s) - 1])
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	soln(n, m)


for _ in range(int(input())):
	Z = list(map(int, input().split()))
	ind = 1 if Z[1] > Z[0] else 0
	s = (str(ind) + str(int(not bool(ind)))) * (Z[int(not bool(ind))] + 1) + str(ind) * (Z[0] != Z[1]) + (str(ind) + str(int(not bool(ind))) + str(ind)) * (Z[ind] - Z[int(not bool(ind))] - 1)
	print(len(s))
	print(s)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n == m:
		ans = (n + 1) * '01'
	elif n > m:
		ans = (m + 1) * '01' + '0' + (n - m - 1) * '010'
	else:
		ans = (n + 1) * '10' + '1' + (m - n - 1) * '101'
	print(len(ans))
	print(ans)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	if n > m:
		a.append(0)
		while n > 0:
			if m <= 0 and a[-1] == 1:
				a.append(0)
				a.append(0)
			a.append(1)
			if m > 0:
				a.append(0)
				m -= 1
			n -= 1
		a.append(0)
	elif n < m:
		a.append(1)
		while m > 0:
			if n <= 0 and a[-1] == 0:
				a.append(1)
				a.append(1)
			a.append(0)
			if n > 0:
				a.append(1)
				n -= 1
			m -= 1
		a.append(1)
	else:
		a.append(0)
		for j in range(n):
			a.append(1)
			a.append(0)
		a.append(1)
	print(len(a))
	for j in a:
		print(j, end='')
	print()


for i in range(int(input())):
	(h, v) = map(int, input().split())
	if h >= v:
		ans = '01' * (v + 1)
		h -= v
		v = 0
		if h > 1:
			ans += '001' * (h - 1)
			h = 1
		if h == 1:
			ans += '0'
		print(len(ans))
		print(ans)
	else:
		ans = '10' * (h + 1)
		v -= h
		h = 0
		if v > 1:
			ans += '110' * (v - 1)
			v = 1
		if v == 1:
			ans += '1'
		print(len(ans))
		print(ans)


for z in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	s = []
	if m <= n:
		for i in range(m + 1):
			s.append('01')
		for i in range(n - m - 1):
			s.append('001')
		if m != n:
			s.append('0')
	else:
		for i in range(n + 1):
			s.append('10')
		for i in range(m - n - 1):
			s.append('110')
		s.append('1')
	s = ''.join(s)
	print(len(s))
	print(s)


for c in range(int(input())):
	(m, n) = [int(k) for k in input().split()]
	an = ''
	if n == m:
		an += '01' * (m + 1)
	elif n > m:
		an += '10' * (m + 1)
		an += '110' * (n - m - 1)
		an += '1'
	else:
		an += '01' * n
		an += '010' * (m - n)
	print(len(an))
	print(an)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = ''
	if n == m:
		ans = '01' * (n + 1)
	elif n < m:
		ans = '10' * (n + 1)
		ans += '110' * (m - n - 1)
		ans += '1'
	else:
		ans = '01' * (m + 1)
		ans += '001' * (n - m - 1)
		ans += '0'
	print(len(ans))
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ons = 0
	zrs = 0
	diff = 0
	if n > m:
		ons = n
		zrs = n + 1
		diff = n - m - 1
		strng = '0'
		for i in range(n):
			if m + 1 > 0:
				m -= 1
				strng += '10'
			else:
				strng += '010'
		print(len(strng), strng, sep='\n')
	elif m > n:
		zrs = m
		ons = m + 1
		diff = m - n - 1
		strng = '1'
		for i in range(m):
			if n + 1 > 0:
				n -= 1
				strng += '01'
			else:
				strng += '101'
		print(len(strng), strng, sep='\n')
	elif m == n:
		zrs = m + 1
		ons = n + 1
		strng = '01'
		for i in range(n):
			strng += '01'
		print(len(strng), strng, sep='\n')


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

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
from collections import Counter

def solve(h, v):
	h1 = h
	v1 = v
	s = '10'
	while h1 > 0 and v1 > 0:
		s = '10' + s
		h1 -= 1
		v1 -= 1
	if h1 == 0:
		if v1 > 0:
			while v1 > 0:
				s = '101' + s
				v1 -= 1
	elif h1 > 0:
		while h1 > 0:
			s = '100' + s
			h1 -= 1
		s = s[2:]
	h1 = h
	v1 = v
	s1 = s
	s = '01'
	while h1 > 0 and v1 > 0:
		s = '01' + s
		h1 -= 1
		v1 -= 1
	if h1 == 0:
		if v1 > 0:
			while v1 > 0:
				s = '011' + s
				v1 -= 1
			s = s[2:]
	elif h1 > 0:
		while h1 > 0:
			s = '010' + s
			h1 -= 1
	num = int(s, 2)
	num1 = int(s1, 2)
	if num1 < num:
		print(len(s1))
		print(s1)
	else:
		print(len(s))
		print(s)
t = int(input())
for _ in range(t):
	(h, v) = integer_list()
	solve(h, v)


t = int(input())
for i in range(0, t):
	(n, m) = list(map(int, input().split(' ')))
	s = ''
	if n > m:
		r = n - m - 1
		answer = 2 * n + 1 + r
		for w in range(0, answer - r):
			if w % 2 == 0:
				if w > 1 and r > 0:
					s = s + '0'
					r = r - 1
				s = s + '0'
			else:
				s = s + '1'
	if n == m:
		answer = 2 * n + 2
		for w in range(0, answer):
			if w % 2 == 0:
				s = s + '0'
			else:
				s = s + '1'
	if n < m:
		r = m - n - 1
		answer = 2 * m + 1 + r
		for w in range(0, answer - r):
			if w % 2 == 0:
				s = s + '1'
				if w > 1 and r > 0:
					s = s + '1'
					r = r - 1
			else:
				s = s + '0'
	print(answer)
	print(s)


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	if N == M:
		Pattern = '01' * (N + 1)
		print(len(Pattern))
		print(Pattern)
	elif N > M:
		Pattern = '01' * M + '010' * (N - M)
		print(len(Pattern))
		print(Pattern)
	elif M > N:
		Pattern = '10' * N + '101' * (M - N)
		print(len(Pattern))
		print(Pattern)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	x = ''
	if m == n:
		for i in range(n + 1):
			x += '01'
	elif m > n:
		for i in range(n + 1):
			x += '10'
		for i in range(m - n - 1):
			x += '110'
		x += '1'
	else:
		for i in range(m):
			x += '01'
		for i in range(n - m):
			x += '010'
	print(len(x))
	print(x)


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	l = 0
	start_char = False
	if N > M:
		l = 1 + 2 * M + 3 * (N - M) - 1
	elif N == M:
		l = 2 * N + 2
	else:
		l = 1 + 2 * N + 3 * (M - N) - 1
		start_char = True
		M = N
	char_list = []
	for i in range(l):
		char_list.append(start_char)
		if i < 2 * M + 1 or (i - 2 * M - 1) % 3 != 1:
			start_char = not start_char
	print(l)
	print(''.join(map(str, map(int, char_list))))


t = int(input())
while t:
	t -= 1
	l = [int(item) for item in input().split(' ')]
	(n, m) = (l[0], l[1])
	if m == n:
		print(2 * (m + 1))
		print('01' * (m + 1))
	elif n > m:
		print(2 * (m + 1) + 3 * (n - (m + 1)) + 1)
		print('01' * (m + 1) + '001' * (n - (m + 1)) + '0')
	else:
		print(2 * (n + 1) + 3 * (m - (n + 1)) + 1)
		print('10' * (n + 1) + '110' * (m - (n + 1)) + '1')


T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	extra_hills_or_valleys = max([N, M]) - min([N, M]) - 1
	length = 2 * min([N, M]) + 3
	N_string = '010'
	M_string = '101'
	string = ''
	if N > M:
		string = '0'
		for l in range(length - 1):
			if string[-1] == '0':
				string = string + '1'
			else:
				string = string + '0'
		string = string + extra_hills_or_valleys * N_string
	elif N < M:
		string = '1'
		for l in range(length - 1):
			if string[-1] == '0':
				string = string + '1'
			else:
				string = string + '0'
		string = string + extra_hills_or_valleys * M_string
	elif N == M:
		length = N + M + 2
		string = '01' * (length // 2)
	if abs(N - M) > 1:
		length += 3 * extra_hills_or_valleys
	print(length)
	print(string)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	if n == m:
		s = '01' * (n + 1)
	elif n > m:
		s = '01' * m + '010' * (n - m)
	else:
		s = '10' * n + '101' * (m - n)
	print(len(s))
	print(s)


from collections import defaultdict as d
for i in range(int(input())):
	(a, b) = map(int, input().split())
	output = ''
	if a == b:
		print(a * 2 + 2)
		output = '01' * (a + 1)
	elif a > b:
		print((b + 1) * 2 + ((a - (b + 1)) * 3 + 1))
		output += '01' * (b + 1)
		output += '001' * (a - (b + 1))
		output += '0'
	else:
		print((a + 1) * 2 + ((b - (a + 1)) * 3 + 1))
		output += '10' * (a + 1)
		output += '110' * (b - (a + 1))
		output += '1'
	print(output)


t = int(input())
for u in range(t):
	(h, v) = map(int, input().split())
	if h == v:
		x = '01' * (h + 1)
		ans = x
	else:
		(m, n) = (min(h, v), max(h, v))
		s = '01' * (m + 1)
		if h > v:
			val = h - v
			s += '0'
			if val > 1:
				s += '010' * (val - 1)
			ans = s
		else:
			val = v - h
			if val > 1:
				ans1 = '1'
				ans2 = '101' * (val - 1)
				ans = ans2 + ans1 + s
			else:
				ans = '1' + s
	print(len(ans))
	print(ans)


try:
	t = int(input())
	while t != 0:
		(n_hills, m_valleys) = [int(i) for i in input().split()]
		if n_hills == m_valleys:
			print(len('01' * (m_valleys + 1)))
			print('01' * (m_valleys + 1))
		elif n_hills > m_valleys:
			print(len('01' * (m_valleys + 1) + '001' * (n_hills - m_valleys - 1) + '0'))
			print('01' * (m_valleys + 1) + '001' * (n_hills - m_valleys - 1) + '0')
		else:
			print(len('10' * (n_hills + 1) + '110' * (m_valleys - n_hills - 1) + '1'))
			print('10' * (n_hills + 1) + '110' * (m_valleys - n_hills - 1) + '1')
		t = t - 1
except Exception:
	pass


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	if n == m:
		ans = '01' * (n + 1)
	elif n > m:
		ans = '01' * (m + 1) + '0' + '010' * (n - m - 1)
	elif n < m:
		ans = '10' * (n + 1) + '1' + '101' * (m - n - 1)
	print(len(ans))
	print(ans)


try:

	def pattern(x, y, total):
		if x >= y:
			st = '01'
			str = st * (total // 2)
			if total % 2 != 0:
				str += '0'
		else:
			st = '10'
			str = st * (total // 2)
			if total % 2 != 0:
				str += '1'
		return str
	for _ in range(int(input())):
		numbers = list(map(int, input().split()))
		x = numbers[0]
		y = numbers[1]
		if x == y:
			total = x + y + 2
			print(total)
			print(pattern(x, y, total))
		elif abs(x - y) == 1:
			total = max(x, y) * 2 + 1
			print(total)
			print(pattern(x, y, total))
		else:
			if x > y:
				arb = min(x, y) + 1
				total = arb * 2 + 1
				str = pattern(arb, y, total)
				c = '010' * (x - arb)
				str += c
			else:
				arb = min(x, y) + 1
				total = arb * 2 + 1
				str = pattern(x, arb, total)
				c = '101' * (y - arb)
				str += c
			print(len(str))
			print(str)
except:
	pass


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n > m:
		print(2 * m + 3 * (n - m))
		print('01' * m + '010' * (n - m))
	elif n == m:
		print(n * 2 + 2)
		print('01' * (n + 1))
	else:
		print(2 * n + 3 * (m - n))
		print('10' * n + '101' * (m - n))


from sys import stdin, stdout
t = int(stdin.readline())
while t != 0:
	(n, m) = map(int, stdin.readline().split())
	if 0 <= n <= 500 and 0 <= m <= 500:
		s = ''
		if n > m:
			s = s + '0'
			for i in range(0, n, 1):
				s = s + '1'
				if m >= 1:
					s = s + '0'
					m = m - 1
				else:
					s = s + '00'
		elif m > n:
			s = s + '1'
			for i in range(0, m, 1):
				s = s + '0'
				if n >= 1:
					s = s + '1'
					n = n - 1
				else:
					s = s + '11'
		else:
			if n == m:
				s = s + '0'
				for i in range(0, n, 1):
					s = s + '10'
			s = s + '11'
	t = t - 1
	s = s[:-1]
	print(len(s))
	print(s)


t = int(input())
for tc in range(t):
	(hills, valleys) = map(int, input().split())
	if valleys > hills:
		terrain = '10' * (hills + 1) + '110' * (valleys - hills - 1) + '1'
	elif hills > valleys:
		terrain = '01' * (valleys + 1) + '001' * (hills - valleys - 1) + '0'
	else:
		terrain = '01' * (hills + 1)
	print(len(terrain))
	print(terrain)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ans = ''
	if n > m:
		ans = ans + '0'
		for i in range(m + 1):
			ans = ans + '1' + '0'
		ans = ans + '010' * (n - (m + 1))
	elif n < m:
		ans = ans + '1'
		for i in range(n + 1):
			ans = ans + '0' + '1'
		ans = ans + '101' * (m - (n + 1))
	else:
		ans = '0'
		for i in range(n):
			ans = ans + '1' + '0'
		ans = ans + '1'
	print(len(ans))
	print(ans)


n = int(input())
for i in range(n):
	(n, m) = map(int, input().split())
	str = ''
	if n > m:
		for i in range(m):
			str += '01'
		for j in range(n - m):
			str += '010'
	elif n < m:
		for i in range(n):
			str += '10'
		for j in range(m - n):
			str += '101'
	elif n == m:
		m = m + 1
		while m != 0:
			str += '0'
			str += '1'
			m = m - 1
	print(len(str))
	print(str)


test_cases = int(input())
for i in range(test_cases):
	(N, M) = tuple(map(int, input().split()))
	res_str = ''
	if N > M:
		res_str = '0' + '10' * M
		if N - M == 1:
			res_str = res_str + '10'
		else:
			res_str = res_str + '10' + '010' * (N - M - 1)
	elif N < M:
		res_str = '1' + '01' * N
		if M - N == 1:
			res_str = res_str + '01'
		else:
			res_str = res_str + '01' + '101' * (M - N - 1)
	elif N == M:
		res_str = '0' + '10' * M + '1'
	print(len(res_str))
	print(res_str)


from collections import Counter
t = int(input())
for _ in range(t):
	(hill, valley) = map(int, input().split())
	res = ''
	if hill > valley:
		res = '01' * valley + '010' * (hill - valley)
	elif valley > hill:
		res = '10' * hill + '101' * (valley - hill)
	else:
		res = '01' * (hill + 1)
	print(len(res))
	print(res)


from collections import Counter
t = int(input())
for _ in range(t):
	(hill, valley) = map(int, input().split())
	res = ''
	left = abs(valley - hill)
	if hill >= valley:
		if hill == valley:
			res += '01'
		while valley != 0:
			res += '01'
			valley -= 1
		while left != 0:
			res += '010'
			left -= 1
	else:
		while hill != 0:
			res += '10'
			hill -= 1
		while left != 0:
			res += '101'
			left -= 1
	print(len(res))
	print(res)


for _ in range(int(input())):
	l = []
	(n, m) = list(map(int, input().split()))
	if n == m:
		for i in range(n + 1):
			l.extend([0, 1])
	elif m > n:
		for i in range(n + 1):
			l.extend([1, 0])
		for i in range(m - n - 1):
			l.extend([1, 1, 0])
		l.append(1)
	else:
		for i in range(m):
			l.extend([0, 1])
		for i in range(n - m):
			l.extend([0, 1, 0])
	print(len(l))
	ls = ''.join((str(x) for x in l))
	print(ls)


t = int(input())
while t > 0:
	str = ''
	l = [int(x) for x in input().split()]
	if l[0] < l[1]:
		for i in range(1, 2 * (l[0] + 1) + 1):
			if i % 2 == 1:
				str = str + '1'
			else:
				str = str + '0'
		l[1] = l[1] - l[0]
		while l[1] > 1:
			str = str + '110'
			l[1] -= 1
		str = str + '1'
		print(len(str))
		print(str)
	elif l[0] > l[1]:
		for i in range(1, 2 * (l[1] + 1) + 1):
			if i % 2 == 1:
				str = str + '0'
			else:
				str = str + '1'
		l[0] = l[0] - l[1]
		while l[0] > 1:
			str = str + '001'
			l[0] -= 1
		str = str + '0'
		print(len(str))
		print(str)
	else:
		for i in range(1, 2 * (l[1] + 1) + 1):
			if i % 2 == 1:
				str = str + '0'
			else:
				str = str + '1'
		print(len(str))
		print(str)
	t -= 1


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	res = ''
	if n > m:
		n = n - m
		while m != 0:
			res += '01'
			m = m - 1
		while n != 0:
			res += '010'
			n = n - 1
	elif m > n:
		m = m - n
		while n != 0:
			res += '10'
			n = n - 1
		while m != 0:
			res += '101'
			m = m - 1
	else:
		while n + 1 != 0:
			res += '01'
			n = n - 1
	print(len(res))
	print(res)


class solution:

	def calc(self, n, m):
		r = ''
		if m == n:
			for i in range(n + 1):
				r += '01'
		elif m > n:
			for j in range(n + 1):
				r += '10'
			for k in range(m - n - 1):
				r += '110'
			r += '1'
		else:
			for i in range(m):
				r += '01'
			for j in range(n - m):
				r += '010'
		print(len(r))
		print(r)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = solution()
	s.calc(n, m)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	out = ''
	if m == n:
		for i in range(m + 1):
			out += '01'
	elif m > n:
		for i in range(n + 1):
			out += '10'
		for i in range(m - n - 1):
			out += '110'
		out += '1'
	else:
		for i in range(m):
			out += '01'
		for i in range(n - m):
			out += '010'
	print(len(out))
	print(out)


t = int(input())

def solution(n, m):
	res = ''
	if m == n:
		for i in range(n + 1):
			res += '01'
	elif m > n:
		for j in range(n + 1):
			res += '10'
		for k in range(m - n - 1):
			res += '110'
		res += '1'
	else:
		for i in range(m):
			res += '01'
		for j in range(n - m):
			res += '010'
	print(len(res))
	print(res)
for i in range(t):
	(n, m) = map(int, input().split())
	solution(n, m)