For each string s consisting of characters '0' and '1' one can define four integers a_00, a_01, a_10 and a_11, where a_{xy} is the number of subsequences of length 2 of the string s equal to the sequence {x, y}. 

In these problem you are given four integers a_00, a_01, a_10, a_11 and have to find any non-empty string s that matches them, or determine that there is no such string. One can prove that if at least one answer exists, there exists an answer of length no more than 1 000 000.


-----Input-----

The only line of the input contains four non-negative integers a_00, a_01, a_10 and a_11. Each of them doesn't exceed 10^9.


-----Output-----

If there exists a non-empty string that matches four integers from the input, print it in the only line of the output. Otherwise, print "Impossible". The length of your answer must not exceed 1 000 000.


-----Examples-----
Input
1 2 3 4

Output
Impossible

Input
1 2 2 1

Output
0110

Source: codeforces | Difficulty: HARD
Tags: Mathematics

Greedy algorithms

Implementation

Constructive algorithms


Solutions:
import sys
import math

def check():
	n = 1000000
	for i in range(n):
		if is_square(1 + 8 * i):
			print(i)

def is_square(integer):
	root = math.sqrt(integer)
	if int(root + 0.5) ** 2 == integer:
		return True
	else:
		return False

def main():
	(a, b, c, d) = map(int, sys.stdin.readline().split())
	if not is_square(1 + 8 * a) or not is_square(1 + 8 * d):
		print('Impossible')
		return
	z = 1 + math.sqrt(1 + 8 * a)
	o = 1 + math.sqrt(1 + 8 * d)
	if z % 2 == 1 or o % 2 == 1:
		print('Impossible')
		return
	z = int(z / 2)
	o = int(o / 2)
	if a == 0 and b == 0 and (c == 0):
		z = 0
	if d == 0 and b == 0 and (c == 0):
		o = 0
	if z * o != b + c:
		print('Impossible')
		return
	if z == 0 and o == 0:
		print(0)
		return
	s = z * o
	ans = []
	while True:
		if s - z >= b:
			ans.append('1')
			s -= z
			o -= 1
		else:
			ans.append('0')
			z -= 1
		if z == 0 and o == 0:
			break
	print(''.join(ans))
main()


import sys, math
(a00, a01, a10, a11) = map(int, input().split())
s = a00 + a01 + a10 + a11
if not s:
	print('1')
	sys.exit()
s = a01 + a10
if a00:
	z = a00 << 1
	x = math.ceil(math.sqrt(z))
	if (x - 1) * x != z:
		print('Impossible')
		sys.exit()
else:
	x = s and 1
if a11:
	z = a11 << 1
	y = math.ceil(math.sqrt(z))
	if (y - 1) * y != z:
		print('Impossible')
		sys.exit()
else:
	y = s and 1
if x * y != s:
	print('Impossible')
	sys.exit()
if s:
	(i, j) = divmod(a10, x)
	print(i * '1', (x - j) * '0', sep='', end='')
	if y > i:
		print('1', j * '0', (y - i - 1) * '1', sep='')
	else:
		print(j * '0')
else:
	print(x * '0', y * '1', sep='')


def impossible():
	print('Impossible')
	exit()

def good(ones, zeros):
	return ones * zeros == a01 + a10
(a00, a01, a10, a11) = map(int, input().split())
if int(round((a00 * 8 + 1) ** 0.5)) ** 2 != a00 * 8 + 1:
	impossible()
if int(round((a11 * 8 + 1) ** 0.5)) ** 2 != a11 * 8 + 1:
	impossible()
zeros = 1 + int(round((a00 * 8 + 1) ** 0.5))
zeros //= 2
ones = 1 + int(round((a11 * 8 + 1) ** 0.5))
ones //= 2
if ones == 1:
	if not good(ones, zeros) and (not good(ones - 1, zeros)):
		impossible()
	elif good(ones - 1, zeros):
		ones -= 1
if zeros == 1:
	if not good(ones, zeros) and (not good(ones, zeros - 1)):
		impossible()
	elif good(ones, zeros - 1) and (not good(ones, zeros)):
		zeros -= 1
if zeros == 0 and ones == 0:
	impossible()
if zeros * ones != a01 + a10:
	impossible()
if zeros != 0:
	start = a10 // zeros
	end = a01 // zeros
	if a01 % zeros == 0 and a10 % zeros == 0:
		print('1' * start + '0' * zeros + '1' * end)
	else:
		a01 %= zeros
		a10 %= zeros
		print('1' * start + a01 * '0' + '1' + a10 * '0' + '1' * end)
else:
	print('1' * ones)


import sys

def BS(x):
	l = 1
	r = 1000000
	while r - l > 1:
		m = (l + r) // 2
		if m * (m - 1) // 2 > x:
			r = m
		else:
			l = m
	if l * (l - 1) // 2 != x:
		print('Impossible')
		sys.exit()
	return l
(a00, a01, a10, a11) = map(int, input().split())
if a00 + a01 + a10 + a11 == 0:
	print('0')
	sys.exit()
c0 = BS(a00)
c1 = BS(a11)
if a00 == 0 or a11 == 0:
	if a01 + a10 == 0:
		if c0 == 1:
			c0 = 0
		if c1 == 1:
			c1 = 0
		print('0' * c0, end='')
		print('1' * c1)
		sys.exit()
if c0 * c1 != a01 + a10:
	print('Impossible')
	sys.exit()
s = list('0' * (c0 + c1))
for i in range(c0 + c1):
	if c0 == 0 or a01 < c1:
		s[i] = '1'
		a10 - +c1
		c1 -= 1
	else:
		a01 -= c1
		c0 -= 1
print(''.join(s))


root = lambda k: int((1 + (1 + 8 * k) ** 0.5) / 2)

def check(k):
	n = root(k)
	return n * (n - 1) / 2 == k

def solve(a00, a01, a10, a11):
	s = a00 + a01 + a10 + a11
	if not check(a00) or not check(a11) or (not check(s)):
		return None
	(x, y, z) = (root(a00), root(a11), root(s))
	if a00 == 0 or a11 == 0:
		if s == 0:
			return '0'
		elif a10 == 0 and a01 == 0:
			return '0' * z if a00 > 0 else '1' * z
		elif a10 + a01 == z - 1:
			return '1' * a10 + '0' + '1' * a01 if a11 > 0 else '0' * a01 + '1' + '0' * a10
		else:
			return None
	if x + y != z:
		return None
	if x == 0:
		if a00 == 0 and a01 == 0 and (a10 == 0):
			return '1' * z
		else:
			return None
	(t, k) = (a10 // x, a10 % x)
	if z - t - x > 0:
		return '1' * t + '0' * (x - k) + '1' + '0' * k + '1' * (z - t - x - 1)
	else:
		return '1' * t + x * '0'
(a00, a01, a10, a11) = [int(x) for x in input().split()]
ans = solve(a00, a01, a10, a11)
if ans is None:
	print('Impossible')
else:
	print(ans)


from collections import defaultdict
import sys, os, math
(a00, a01, a10, a11) = map(int, input().split())
(x, y) = (int((1 + math.sqrt(1 + 8 * a11)) // 2), int((1 + math.sqrt(1 + 8 * a00)) // 2))
if a11 + a10 + a01 + a00 == 0:
	print(1)
	sys.exit(0)
elif a11 + a10 + a01 == 0 and y * (y - 1) // 2 == a00:
	print('0' * y)
	sys.exit(0)
elif a00 + a10 + a01 == 0 and x * (x - 1) // 2 == a11:
	print('1' * x)
	sys.exit(0)
if y * (y - 1) // 2 != a00 or x * (x - 1) // 2 != a11 or x * y != a10 + a01:
	print('Impossible')
	sys.exit(0)
l = x - math.ceil((x * y - a10) / y)
r = (x * y - a10) // y
diff = a10 - l * y
if diff == 0:
	print('1' * l + '0' * y + '1' * r)
else:
	print('1' * l + '0' * (y - diff) + '1' + '0' * diff + '1' * r)


import sys
import math

def read_data():
	return tuple(map(int, next(sys.stdin).split()))

def reverse_count(k):
	d = math.sqrt(1 + 8 * k)
	n = int((1 + d) / 2 + 0.5)
	if n * (n - 1) == 2 * k:
		return n
	return None

def solve1(a, b, x01, x10):
	if x01 + x10 != a * b:
		return None
	characters = []
	while a > 0 or b > 0:
		if a >= 1 and x01 >= b:
			a -= 1
			x01 -= b
			characters.append('0')
		elif b >= 1 and x10 >= a:
			b -= 1
			x10 -= a
			characters.append('1')
		else:
			return None
	return ''.join(characters)

def solve(x00, x01, x10, x11):
	if x00 == 0:
		if x11 == 0:
			if x01 == x10 == 0:
				return '0'
			return solve1(1, 1, x01, x10)
		b = reverse_count(x11)
		if b is not None:
			return solve1(0, b, x01, x10) or solve1(1, b, x01, x10)
		return None
	if x11 == 0:
		a = reverse_count(x00)
		if a is not None:
			return solve1(a, 0, x01, x10) or solve1(a, 1, x01, x10)
		return None
	a = reverse_count(x00)
	b = reverse_count(x11)
	if a is not None and b is not None:
		return solve1(a, b, x01, x10)
	return None
(x00, x01, x10, x11) = read_data()
s = solve(x00, x01, x10, x11)
if s is None:
	print('Impossible')
else:
	print(s)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(a, b, c, d) = map(int, input().split())
one = -1
zer = -1

def find(on, ze):
	if b + c != on * ze or on + ze == 0:
		return False
	s01 = ze * on
	ind = [i for i in range(ze, ze + on)]
	cou = 0
	while s01 > b:
		t = min(s01 - b, ze)
		ind[cou] -= t
		s01 -= t
		cou += 1
		if cou == len(ind):
			break
	if s01 != b:
		return False
	ind = set(ind)
	ans = []
	for i in range(ze + on):
		if i in ind:
			ans.append(1)
		else:
			ans.append(0)
	print(*ans, sep='')
	return True
for i in range(100001):
	if i * (i - 1) // 2 == a:
		zer = i
	if i * (i - 1) // 2 == d:
		one = i
if one == -1 or zer == -1:
	print('Impossible')
	sys.exit(0)
if one == 1:
	try1 = [0, 1]
else:
	try1 = [one]
if zer == 1:
	try0 = [0, 1]
else:
	try0 = [zer]
for i in try1:
	for j in try0:
		f = find(i, j)
		if f == True:
			sys.exit(0)
print('Impossible')


(a00, a01, a10, a11) = list(map(int, input().split()))
if sum([a00, a01, a10, a11]) == 0:
	print(0)
	exit(0)
(z, j) = (0, 0)
if a01 != 0 or a10 != 0:
	z = j = 1
while z * (z - 1) // 2 < a00:
	z += 1
while j * (j - 1) // 2 < a11:
	j += 1
if any([z * (z - 1) // 2 != a00, j * (j - 1) // 2 != a11, z * j != a10 + a01]):
	print('Impossible')
	exit(0)
n = z + j
for i in range(n):
	if z > 0 and a01 >= j:
		print('0', end='')
		a01 -= j
		z -= 1
	else:
		print('1', end='')
		j -= 1


f = lambda q: 1 + int((1 + 8 * q) ** 0.5) >> 1
(a, b, c, d) = map(int, input().split())
(x, y) = (f(a), f(d))
if x * x - x - 2 * a or y * y - y - 2 * d:
	t = 'Impossible'
elif a + b + c == 0:
	t = '1' * y
elif b + c + d == 0:
	t = '0' * x
elif b + c - x * y:
	t = 'Impossible'
elif c:
	t = '1' * (y - b // x - 1) + '0' * (b % x) + '1' + '0' * (x - b % x) + '1' * (b // x)
else:
	t = '0' * x + '1' * y
print(t)


import sys
import bisect

def check(s, *b):
	cnt = [0, 0]
	a = [0, 0, 0, 0]
	for c in s:
		cnt[int(c)] += 1
	a[0] = cnt[0] * (cnt[0] - 1) // 2
	a[3] = cnt[1] * (cnt[1] - 1) // 2
	for c in s:
		cnt[int(c)] -= 1
		if c == '1':
			a[2] += cnt[0]
		else:
			a[1] += cnt[1]
	for i in range(4):
		if a[i] != b[i]:
			return False
	return True

def solve(n0, n1, a01, a10):
	if a01 + a10 != n0 * n1:
		return []
	if n0 == 0:
		return '1' * n1
	if n1 == 0:
		return '0' * n0
	cnt1 = a10 // n0
	cnt2 = a10 - cnt1 * n0
	cnt3 = n1 - cnt1 - (1 if cnt2 > 0 else 0)
	ans = '1' * cnt1
	ans += '0' * (n0 - cnt2)
	if cnt2 > 0:
		ans += '1'
	ans += '0' * cnt2
	ans += '1' * cnt3
	return ans
(a00, a01, a10, a11) = [int(x) for x in input().split()]
n0 = [0, 1]
n1 = [0, 1]
if a00 > 0:
	z = int(((8 * a00 + 1) ** 0.5 + 1) / 2)
	if z * (z - 1) // 2 != a00:
		print('Impossible')
		sys.exit()
	n0 = [z]
if a11 > 0:
	z = int(((8 * a11 + 1) ** 0.5 + 1) / 2)
	if z * (z - 1) // 2 != a11:
		print('Impossible')
		sys.exit()
	n1 = [z]
for x in n0:
	for y in n1:
		z = solve(x, y, a01, a10)
		if len(z) > 0:
			print(z)
			sys.exit()
print('Impossible')


def main():
	from itertools import product

	def f(a):
		x = int((a * 2.0 + 0.25) ** 0.5 + 0.51)
		if x * (x - 1) != a * 2:
			raise ValueError
		return (x,) if a else (1, 0)
	(a00, a01, a10, a11) = list(map(int, input().split()))
	try:
		for (b, w) in product(f(a00), f(a11)):
			if b * w == a01 + a10:
				break
		else:
			raise ValueError
	except ValueError:
		print('Impossible')
	else:
		(a01, rest) = divmod(a01, w) if w else (b, 0)
		if rest:
			l = ['0' * a01, '1' * (w - rest), '0', '1' * rest, '0' * (b - a01 - 1)]
		else:
			l = ['0' * a01, '1' * w, '0' * (b - a01)]
		print(''.join(l))

def __starting_point():
	main()
__starting_point()


from math import *
from sys import *

def calc(f):
	return int((1 + sqrt(8 * f + 1)) // 2)
(a, b, c, d) = (int(z) for z in input().split())
if a == d == 0 and b == 1 and (c == 0):
	print('01')
	exit(0)
if a == d == 0 and b == 0 and (c == 1):
	print('10')
	exit(0)
if a == d == 0:
	if b + c != 0:
		print('Impossible')
		exit(0)
	print(0)
	exit(0)
if a == 0:
	if sqrt(8 * d + 1) != int(sqrt(8 * d + 1)):
		print('Impossible')
		exit(0)
	if b == c == 0:
		ans = '1' * calc(d)
		print(ans)
	else:
		if b + c != calc(d):
			print('Impossible')
			exit(0)
		ans = c * '1' + '0' + b * '1'
		print(ans)
	exit(0)
if d == 0:
	if sqrt(8 * a + 1) != int(sqrt(8 * a + 1)):
		print('Impossible')
		exit(0)
	if b == c == 0:
		ans = '0' * calc(a)
		print(ans)
	else:
		if b + c != calc(a):
			print('Impossible')
			exit(0)
		ans = b * '0' + '1' + c * '0'
		print(ans)
	exit(0)
if sqrt(8 * d + 1) != int(sqrt(8 * d + 1)):
	print('Impossible')
	exit(0)
if sqrt(8 * a + 1) != int(sqrt(8 * a + 1)):
	print('Impossible')
	exit(0)
x = calc(a)
y = calc(d)
if x * y != b + c:
	print('Impossible')
	exit(0)
ans = ''
res = 0
while res + x <= c:
	ans += '1'
	y -= 1
	res += x
while res + x != c:
	ans += '0'
	x -= 1
if res != c:
	ans += '1'
	y -= 1
while x:
	x -= 1
	ans += '0'
while y:
	y -= 1
	ans += '1'
print(ans)


(a00, a01, a10, a11) = map(int, input().split())
numZeros = 0
numOnes = 0
ans = True
for n0 in range(1, 2 * a00 + 1):
	if n0 * (n0 - 1) == 2 * a00:
		numZeros = n0
		break
	elif n0 * (n0 - 1) > 2 * a00:
		ans = False
		break
for n1 in range(1, 2 * a11 + 1):
	if n1 * (n1 - 1) == 2 * a11:
		numOnes = n1
		break
	elif n1 * (n1 - 1) > 2 * a11:
		ans = False
		break
res = []

def generateResult(x, a01, a10, n0, n1):
	while n0 > 0 or n1 > 0:
		if a01 >= n1 and n1 > 0:
			if n0 >= 1:
				res.append(0)
				a01 = a01 - n1
				n0 = n0 - 1
			else:
				return
		elif a10 >= n0 and n0 > 0:
			if n1 >= 1:
				res.append(1)
				a10 = a10 - n0
				n1 = n1 - 1
			else:
				return
		elif n0 > 0 and n1 > 0:
			return
		elif 0 < n0 == a01 + a10 + n0 + n1:
			for i in range(n0):
				res.append(0)
			n0 = 0
		elif 0 < n1 == a01 + a10 + n0 + n1:
			for i in range(n1):
				res.append(1)
			n1 = 0
		else:
			return
if a01 > 0 or a10 > 0:
	numOnes = max(numOnes, 1)
	numZeros = max(numZeros, 1)
if a00 == a01 == a10 == a11 == 0:
	print(1)
elif a11 == 0 and a00 == 0 and (a10 == 1) and (a01 == 0):
	print('10')
elif a11 == 0 and a00 == 0 and (a01 == 1) and (a10 == 0):
	print('01')
elif ans:
	generateResult(res, a01, a10, numZeros, numOnes)
	if len(res) == numZeros + numOnes:
		print(''.join(map(str, res)))
	else:
		print('Impossible')
else:
	print('Impossible')


def F(s):
	x00 = x01 = x10 = x11 = 0
	for i in range(len(s)):
		for j in range(i + 1, len(s)):
			cur = s[i] + s[j]
			if cur == '00':
				x00 += 1
			if cur == '01':
				x01 += 1
			if cur == '10':
				x10 += 1
			if cur == '11':
				x11 += 1
	return (x00, x01, x10, x11)

def F2(s):
	x00 = x01 = x10 = x11 = 0
	c0 = s.count(0)
	c1 = s.count(1)
	x00 = c0 * (c0 - 1) // 2
	x11 = c1 * (c1 - 1) // 2
	cur0 = 0
	cur1 = 0
	for i in range(len(s)):
		if s[i] == 0:
			x10 += cur1
			cur0 += 1
		else:
			x01 += cur0
			cur1 += 1
	return (x00, x01, x10, x11)

def fail():
	print('Impossible')
	exit()
(a00, a01, a10, a11) = map(int, input().split())
f = lambda x: x * (x - 1) // 2
(L, R) = (0, 10 ** 6)
while R - L > 1:
	M = (L + R) // 2
	if f(M) >= a00:
		R = M
	else:
		L = M
c0 = R
(L, R) = (0, 10 ** 6)
while R - L > 1:
	M = (L + R) // 2
	if f(M) >= a11:
		R = M
	else:
		L = M
c1 = R
if a00 == 0 and a11 == 0:
	if (a01, a10) == (1, 0):
		s = [0, 1]
	elif (a01, a10) == (0, 1):
		s = [1, 0]
	elif (a01, a10) == (0, 0):
		s = [1]
	else:
		fail()
	print(''.join(map(str, s)))
	exit()
elif a00 == 0:
	if (a01, a10) == (0, 0):
		c0 = 0
elif a11 == 0:
	if (a01, a10) == (0, 0):
		c1 = 0
s = [0] * c0 + [1] * c1
b01 = c0 * c1
if b01 != a01 + a10:
	fail()
for i in range(c1):
	if b01 - c0 < a01:
		j = i + c0
		break
	b01 -= c0
	(s[i], s[i + c0]) = (s[i + c0], s[i])
while b01 > a01:
	(s[j], s[j - 1]) = (s[j - 1], s[j])
	b01 -= 1
	j -= 1
if F2(s) != (a00, a01, a10, a11):
	fail()
print(''.join(map(str, s)))


import math
(a00, a01, a10, a11) = [int(i) for i in input().split()]
done = 0
if a00 == 0 and a11 == 0:
	if a01 + a10 > 1:
		print('Impossible')
		done = 1
if not done:
	N0 = (1 + math.sqrt(1 + 8 * a00)) / 2
	N1 = (1 + math.sqrt(1 + 8 * a11)) / 2
	if a00 == 0 and N1 == int(N1):
		if a01 == 0 and a10 == 0:
			print('1' * int(N1))
		elif a01 + a10 == N1:
			print(a10 * '1' + '0' + a01 * '1')
		else:
			print('Impossible')
	elif a11 == 0 and N0 == int(N0):
		if a01 == 0 and a10 == 0:
			print('0' * int(N0))
		elif a01 + a10 == N0:
			print(a01 * '0' + '1' + a10 * '0')
		else:
			print('Impossible')
	elif N0 * N1 != a01 + a10 or int(N1) != N1 or int(N0) != N0:
		print('Impossible')
	else:
		N0 = int(N0)
		N1 = int(N1)
		(divisor, remainder) = divmod(a10, N0)
		s = '1' * divisor + (N0 - remainder) * '0'
		if remainder != 0:
			s += '1' + remainder * '0'
			N1 -= 1
		s += (N1 - divisor) * '1'
		print(s)


def build(a0, a1, a01, a10, arr):
	while True:
		if a0 + a1 == 0 and a01 + a10 > 0:
			return (False, '')
		if a01 < a1 and a10 < a0:
			return (False, '')
		if a01 + a10 == 0:
			if a0 > 0 and a1 > 0:
				return (False, '')
			while a0 > 0:
				arr.append(0)
				a0 -= 1
			while a1 > 0:
				arr.append(1)
				a1 -= 1
			return (True, arr)
		if a01 >= a1:
			arr.append(0)
			a0 -= 1
			a01 -= a1
		else:
			arr.append(1)
			a1 -= 1
			a10 -= a0
val = [0] * 50000
for i in range(1, 50000):
	val[i] = i * (i - 1) // 2
d = {x: i for (i, x) in enumerate(val)}
(a00, a01, a10, a11) = map(int, input().split())

def solve(a00, a01, a10, a11):
	a0_arr = []
	a1_arr = []
	ans = None
	flag = False
	if a00 == 0:
		a0_arr = [0, 1]
	else:
		if a00 not in d:
			return (flag, ans)
		a0_arr.append(d[a00])
	if a11 == 0:
		a1_arr = [0, 1]
	else:
		if a11 not in d:
			return (flag, ans)
		a1_arr.append(d[a11])
	for a0 in a0_arr:
		for a1 in a1_arr:
			arr = []
			(flg, arr) = build(a0, a1, a01, a10, arr)
			if flg == True:
				flag = flg
				ans = arr
				break
	return (flag, ans)
(flag, ans) = solve(a00, a01, a10, a11)
if flag == False:
	print('Impossible')
else:
	print(''.join([str(x) for x in ans]))


import math

def get_cnt(res):
	n = 1 + math.floor(math.sqrt(2 * res))
	if n * (n - 1) / 2 == res:
		return n
	else:
		return -1

def calc():
	cnt = list(map(int, input().split()))
	if cnt == [0, 0, 0, 0]:
		return '0'
	a = get_cnt(cnt[0])
	b = get_cnt(cnt[3])
	if cnt == [0, 0, 0, cnt[3]]:
		a = 0
	if cnt == [cnt[0], 0, 0, 0]:
		b = 0
	if a == -1 or b == -1 or a * b != cnt[1] + cnt[2]:
		return 'Impossible'
	ans = ['0'] * (a + b)
	i = 0
	while b > 0:
		while cnt[1] >= b:
			i = i + 1
			cnt[1] -= b
		b -= 1
		ans[i] = '1'
		i += 1
	return ''.join(ans)
print(calc())