AIM Tech Round 3 (Div. 2)D. Recover the String（贪心+字符串）

For each string s consisting of characters '0' and '1' one can define four integers a00, a01, a10 and a11, where axy 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 a00, a01, a10, a11 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 a00, a01, a10 and a11. Each of them doesn't exceed109.

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

比赛时，一直纠结怎么判断Impossible和构造字符串，胡乱交了一发，wa了，好SB。

当然先是利用a00和a11求1和0的字符串个数g1和g0，如果a00或a11等于1，这时候还要根据a10和a01判断a00或者a11是等于1还是0.

在求完a00和a11的个数后，判断合不合理，C(g0,2)=a00, C(g1,2)=a11, C(g1+g0,2) = a00+a01+a10+a11即成立。

然后就是构造字符串了。

设初始的字符串个数为0000001111111......

然后就是贪心的构造字符串了。考虑该输出某一位时，如果在这一位时，a10>=g0,那么我可以把1挪到最前面，输出1，这时候后面剩下的字符串需要构造的a10-=g0,剩余的1的个数g1--。否则直接输出0，后面剩余字符串需要构造a01-=g1,剩余的0的个数g0--.

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 int main()
 9 {
10     ll a00,a01,a10,a11;
11     scanf("%I64d%I64d%I64d%I64d",&a00,&a01,&a10,&a11);
12     ll g0,g1;
13     g0 = (1+sqrt(1+8*a00))/2;
14     g1 = (1+sqrt(1+8*a11))/2;
15     if(a00+a01+a10+a11==0)
16     {
17          printf("0
");
18          return 0;
19     }
20     if(g0==1||g1==1)
21     {
22         if(g0==1)
23         {
24             if(a01||a10) g0 = 1;
25             else g0 = 0;
26         }
27         if(g1==1)
28         {
29             if(a01||a10) g1 = 1;
30             else g1 = 0;
31         }
32     }
33     if(g0*(g0-1)!=2*a00||g1*(g1-1)!=2*a11)
34     {
35         printf("Impossible
");
36         return 0;
37     }
38     ll gz = g0+g1;
39     if(gz*(gz-1)/2!=(a00+a01+a10+a11))
40     {
41         printf("Impossible
");
42         return 0;
43     }
44     while(g0+g1)
45     {
46         if(a10>=g0)
47         {
48             printf("1");
49             a10 -= g0;
50             g1--;
51         }
52         else
53         {
54             printf("0");
55             a01 -= g1;
56             g0--;
57         }
58     }
59     printf("
");
60     return 0;
61 }