Define the score of some binary string $T$ as the absolute difference between the number of zeroes and ones in it. (for example, $T=$ 010001 contains $4$ zeroes and $2$ ones, so the score of $T$ is $|4-2| = 2$).

Define the creepiness of some binary string $S$ as the maximum score among all of its prefixes (for example, the creepiness of $S=$ 01001 is equal to $2$ because the score of the prefix $S[1 \ldots 4]$ is $2$ and the rest of the prefixes have a score of $2$ or less).

Given two integers $a$ and $b$, construct a binary string consisting of $a$ zeroes and $b$ ones with the minimum possible creepiness.


-----Input-----

The first line contains a single integer $t$ $(1\le t\le 1000)$  — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $a$ and $b$ ($ 1 \le a, b \le 100$)  — the numbers of zeroes and ones correspondingly.


-----Output-----

For each test case, print a binary string consisting of $a$ zeroes and $b$ ones with the minimum possible creepiness. If there are multiple answers, print any of them.


-----Examples-----

Input
5
1 1
1 2
5 2
4 5
3 7
Output
10
011
0011000
101010101
0001111111


-----Note-----

In the first test case, the score of $S[1 \ldots 1]$ is $1$, and the score of $S[1 \ldots 2]$ is $0$.

In the second test case, the minimum possible creepiness is $1$ and one of the other answers is 101.

In the third test case, the minimum possible creepiness is $3$ and one of the other answers is 0001100.

Source: codeforces | Difficulty: EASY
Tags: Implementation

Greedy algorithms


Solutions:
t = int(input())
while t > 0:
	t -= 1
	(a, b) = map(int, input().split())
	mn = min(a, b)
	s = '01' * mn
	a -= mn
	b -= mn
	s += '0' * a + '1' * b
	print(s)


t = int(input())
for _ in range(t):
	(a, b) = list(map(int, input().split()))
	s = '01' * min(a, b) + '1' * (b - min(a, b)) + '0' * (a - min(a, b))
	print(s)


z = int(input())
while z > 0:
	(x, y) = map(int, input().split())
	print('01' * min(x, y) + '0' * max(0, x - y) + '1' * max(0, y - x))
	z = z - 1


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	s = ''
	if a >= b:
		s += '01' * b
		s += '0' * (a - b)
	else:
		s += '01' * a
		s += '1' * (b - a)
	print(s)


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

def shift(s):
	for i in range(1, len(s) + 1):
		if s == s[i:] + s[:i]:
			return i

def prefix(a):
	res = [0]
	for num in a:
		res.append(res[-1] + num)
	return res
for _ in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	c = '0' if a > b else '1'
	print('01' * min(a, b) + c * max(a - b, b - a))


for _ in range(int(input())):
	(z, o) = map(int, input().split())
	if z == o:
		print('01' * z)
	elif z > o:
		print('01' * o + '0' * (z - o))
	else:
		print('01' * z + '1' * (o - z))


tcs = 1
tcs = int(input())
for tc in range(tcs):
	(a, b) = map(int, input().split())
	ans = ''
	ans += '01' * min(a, b)
	diff = abs(a - b)
	if a > b:
		ans += '0' * diff
	elif b > a:
		ans += '1' * diff
	else:
		pass
	print(ans)


for _ in range(int(input())):
	(n0, n1) = map(int, input().split())
	print('01' * min(n0, n1) + '1' * max(0, n1 - n0) + '0' * max(0, n0 - n1))


t = int(input())
for tt in range(t):
	(a, b) = map(int, input().split())
	if a > b:
		print('01' * b + '0' * (a - b))
	else:
		print('01' * a + '1' * (b - a))


n = int(input().strip())
for _ in range(n):
	input_line = input().strip().split(' ')
	a = int(input_line[0])
	b = int(input_line[1])
	res = ''
	res += '01' * min(a, b)
	if a > b:
		res += '0' * (a - b)
	else:
		res += '1' * (b - a)
	print(res)


def func():
	(a, b) = map(int, input().split())
	s = ''
	if a < b:
		for i in range(a):
			s += '0'
			s += '1'
		if b - a > 0:
			for i in range(b - a):
				s += '1'
	else:
		for i in range(b):
			s += '0'
			s += '1'
		if a - b > 0:
			for i in range(a - b):
				s += '0'
	print(s)
t = int(input())
for _ in range(t):
	func()


t = int(input())
while t:
	t -= 1
	inp = list(map(int, input().split()))
	a = inp[0]
	b = inp[1]
	ans = ''
	z = min(a, b)
	for i in range(z):
		ans += '01'
	for i in range(z, a):
		ans += '0'
	for i in range(z, b):
		ans += '1'
	print(ans)


for _ in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	if a > b:
		ans = ''
		ans += '01' * b
		ans += '0' * (a - b)
	else:
		ans = ''
		ans += '01' * a
		ans += '1' * (b - a)
	print(ans)


test = int(input())
for _ in range(test):
	arr = list(map(int, input().split()))
	a = arr[0]
	b = arr[1]
	ansStr = ''
	for i in range(min(a, b)):
		ansStr = ansStr + '01'
	if a > b:
		add = a - b
		ansStr += '0' * add
	else:
		add = b - a
		ansStr += '1' * add
	print(ansStr)


import sys
input = lambda : sys.stdin.readline().strip()
t = int(input())
for i in range(t):
	(l, r) = list(map(int, input().split()))
	x = '01'
	y = '10'
	x1 = '1'
	y1 = '0'
	if l == r:
		print(x * l)
	elif min(l, r) == l:
		print(x * l + x1 * (r - l))
	else:
		print(x * r + y1 * (l - r))


t = int(input())
for _ in range(t):
	(a, b) = [int(x) for x in input().split()]
	if a == b:
		s = '01' * a
	elif a > b:
		s = '01' * b + '0' * (a - b)
	else:
		s = '01' * a + '1' * (b - a)
	print(s)


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


for i in range(int(input())):
	(A, B) = map(int, input().split())
	z = '01' * min(A, B) + '0' * max(0, A - B) + '1' * max(0, B - A)
	print(z)


import sys
import collections
import heapq
import bisect
import math
from collections import Counter
from functools import lru_cache
sys.setrecursionlimit(10 ** 6)
for _ in range(int(input())):
	(a, b) = list(map(int, sys.stdin.readline().split()))
	if a == b:
		print('01' * a)
	elif a > b:
		x = a - b
		print('01' * b + '0' * x)
	else:
		x = b - a
		print('01' * a + '1' * x)


import sys
input = lambda : sys.stdin.readline().strip()

def new_func(input):
	for _ in ' ' * int(input()):
		(a, b) = map(int, input().split())
		count = ''
		while True:
			if a > 0:
				count += '0'
				a -= 1
			if b > 0:
				count += '1'
				b -= 1
			if a == 0 and b == 0:
				break
		print(count)
new_func(input)


t = int(input())
while t:
	(a, b) = map(int, input().split())
	print('01' * min(a, b) + '0' * max(0, a - b) + '1' * max(0, b - a))
	t -= 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print('01' * min(a, b) + ((a - b) * '0' if a > b else (b - a) * '1'))


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	ans = ''
	for j in range(min(a, b)):
		ans += '01'
	if a > b:
		ans += '0' * (a - b)
	else:
		ans += '1' * (b - a)
	print(ans)