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

Difficulty: competition

Starter code:

Solutions:
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())


def main():
    from itertools import product
    def f(a):
        x = int((a * 2. + .25) ** .5 + .51)
        if x * (x - 1) != a * 2:
            raise ValueError
        return x

    a00, a01, a10, a11 = list(map(int, input().split()))
    try:
        for b, w in product([f(a00)] if a00 else [1, 0], [f(a11)] if a11 else [1, 0]):
            if b * w == a01 + a10:
                break
        else:
            raise ValueError
    except ValueError:
        print("Impossible")
    else:
        if w:
            a01, rest = divmod(a01, w)
            if rest:
                l = ['0' * a01, '1' * (w - rest), '0', '1' * rest, '0' * (b - a01 - 1)]
            else:
                l = ['0' * a01, '1' * w, '0' * (b - a01)]
        else:
            l = ['0' * b]
        print(''.join(l))


def __starting_point():
    main()

__starting_point()

def main():
    from itertools import product
    def f(a):
        x = int((a * 2. + .25) ** .5 + .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()

def build(a0, a1, a01, a10, arr):
    #print(a0, a1, a01, a10)
    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]))

a00, a01, a10, a11 = list(map(int, input().split()))
 
if sum([a00, a01, a10, a11]) == 0:
    print(0)
    return
 
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')
    return
 
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