#include <bits/stdc++.h>
using namespace std;
bool can(int c0, int c1, int ck, int n0, int n1, int k) {
  return c0 <= n0 && c1 <= n1 && ck <= k && k >= ck + c1 * (n0 - c0) &&
         k <= ck + (n0 - c0) * (n1 - c1) + c1 * (n0 - c0);
}
string solve(int a00, int a01, int a10, int a11) {
  if (int64_t(a00) + a01 + a10 + a11 == 0) {
    return "0";
  }
  int n0 = int((sqrt(8.0 * a00 + 1) + 1) / 2);
  int n1 = int((sqrt(8.0 * a11 + 1) + 1) / 2);
  if (a01 == 0 && a10 == 0 && a00 == 0) {
    --n0;
  } else if (a01 == 0 && a10 == 0 && a11 == 0) {
    --n1;
  }
  int k = a10;
  if (a01 != n0 * n1 - k || k > n0 * n1 || a00 != n0 * (n0 - 1) / 2 ||
      a11 != n1 * (n1 - 1) / 2) {
    return "Impossible";
  }
  string s;
  int c0 = 0, c1 = 0, ck = 0;
  for (int i = 0; i < n0 + n1; ++i) {
    int c0_0 = c0 + 1, c1_0 = c1, k_0 = c1 + ck;
    int c0_1 = c0, c1_1 = c1 + 1, k_1 = ck;
    if (can(c0_0, c1_0, k_0, n0, n1, k)) {
      c0 = c0_0;
      c1 = c1_0;
      ck = k_0;
      s.push_back('0');
    } else {
      c0 = c0_1;
      c1 = c1_1;
      ck = k_1;
      s.push_back('1');
    }
  }
  return s;
}
bool check(int a00, int a01, int a10, int a11, string const& s) {
  int c00 = 0, c01 = 0, c10 = 0, c11 = 0;
  for (int i = 0; i < s.size(); ++i) {
    for (int j = i + 1; j < s.size(); ++j) {
      if (s[i] == '0' && s[j] == '0') {
        ++c00;
      } else if (s[i] == '0' && s[j] == '1') {
        ++c01;
      } else if (s[i] == '1' && s[j] == '0') {
        ++c10;
      } else if (s[i] == '1' && s[j] == '1') {
        ++c11;
      }
    }
  }
  return c00 == a00 && c01 == a01 && c10 == a10 && c11 == a11 &&
         s.length() <= 1000000;
}
int main() {
  int a00, a01, a10, a11;
  cin >> a00 >> a01 >> a10 >> a11;
  string result = solve(a00, a01, a10, a11);
  cout << result << endl;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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 exceed 109.

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool can(int c0, int c1, int ck, int n0, int n1, int k) {
  return c0 <= n0 && c1 <= n1 && ck <= k && k >= ck + c1 * (n0 - c0) &&
         k <= ck + (n0 - c0) * (n1 - c1) + c1 * (n0 - c0);
}
string solve(int a00, int a01, int a10, int a11) {
  if (int64_t(a00) + a01 + a10 + a11 == 0) {
    return "0";
  }
  int n0 = int((sqrt(8.0 * a00 + 1) + 1) / 2);
  int n1 = int((sqrt(8.0 * a11 + 1) + 1) / 2);
  if (a01 == 0 && a10 == 0 && a00 == 0) {
    --n0;
  } else if (a01 == 0 && a10 == 0 && a11 == 0) {
    --n1;
  }
  int k = a10;
  if (a01 != n0 * n1 - k || k > n0 * n1 || a00 != n0 * (n0 - 1) / 2 ||
      a11 != n1 * (n1 - 1) / 2) {
    return "Impossible";
  }
  string s;
  int c0 = 0, c1 = 0, ck = 0;
  for (int i = 0; i < n0 + n1; ++i) {
    int c0_0 = c0 + 1, c1_0 = c1, k_0 = c1 + ck;
    int c0_1 = c0, c1_1 = c1 + 1, k_1 = ck;
    if (can(c0_0, c1_0, k_0, n0, n1, k)) {
      c0 = c0_0;
      c1 = c1_0;
      ck = k_0;
      s.push_back('0');
    } else {
      c0 = c0_1;
      c1 = c1_1;
      ck = k_1;
      s.push_back('1');
    }
  }
  return s;
}
bool check(int a00, int a01, int a10, int a11, string const& s) {
  int c00 = 0, c01 = 0, c10 = 0, c11 = 0;
  for (int i = 0; i < s.size(); ++i) {
    for (int j = i + 1; j < s.size(); ++j) {
      if (s[i] == '0' && s[j] == '0') {
        ++c00;
      } else if (s[i] == '0' && s[j] == '1') {
        ++c01;
      } else if (s[i] == '1' && s[j] == '0') {
        ++c10;
      } else if (s[i] == '1' && s[j] == '1') {
        ++c11;
      }
    }
  }
  return c00 == a00 && c01 == a01 && c10 == a10 && c11 == a11 &&
         s.length() <= 1000000;
}
int main() {
  int a00, a01, a10, a11;
  cin >> a00 >> a01 >> a10 >> a11;
  string result = solve(a00, a01, a10, a11);
  cout << result << endl;
}

```