#include <bits/stdc++.h>
using namespace std;
const int inf = ~0U >> 1;
const long long linf = (long long)1e18;
const double eps = 1e-6;
template <class T>
string tostr(T a) {
  ostringstream out;
  out << a;
  return out.str();
}
struct debugger {
  template <typename T>
  debugger &operator,(const T &x) {
    cerr << x << endl;
    return *this;
  }
} dbg;
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
}
inline void read(long long &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
}
inline void read(double &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (ch == '.') {
    double tmp = 1;
    ch = nc();
    for (; ch >= '0' && ch <= '9'; ch = nc())
      tmp /= 10.0, x += tmp * (ch - '0');
  }
  if (sign) x = -x;
}
inline void read(char *s) {
  char ch = nc();
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  for (; !blank(ch) && !IOerror; ch = nc()) *s++ = ch;
  *s = 0;
}
inline void read(char &c) {
  for (c = nc(); blank(c); c = nc())
    ;
  if (IOerror) {
    c = -1;
    return;
  }
}
inline void read1(int &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (bo) x = -x;
}
inline void read1(long long &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (bo) x = -x;
}
inline void read1(double &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (ch == '.') {
    double tmp = 1;
    for (ch = getchar(); ch >= '0' && ch <= '9';
         tmp /= 10.0, x += tmp * (ch - '0'), ch = getchar())
      ;
  }
  if (bo) x = -x;
}
inline void read1(char *s) {
  char ch = getchar();
  for (; blank(ch); ch = getchar())
    ;
  for (; !blank(ch); ch = getchar()) *s++ = ch;
  *s = 0;
}
inline void read1(char &c) {
  for (c = getchar(); blank(c); c = getchar())
    ;
}
inline void read2(int &x) { scanf("%d", &x); }
inline void read2(long long &x) { scanf("%lld", &x); }
inline void read2(double &x) { scanf("%lf", &x); }
inline void read2(char *s) { scanf("%s", s); }
inline void read2(char &c) { scanf(" %c", &c); }
inline void readln2(char *s) { gets(s); }
struct Ostream_fwrite {
  char *buf, *p1, *pend;
  Ostream_fwrite() {
    buf = new char[100000];
    p1 = buf;
    pend = buf + 100000;
  }
  void out(char ch) {
    if (p1 == pend) {
      fwrite(buf, 1, 100000, stdout);
      p1 = buf;
    }
    *p1++ = ch;
  }
  void print(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
  }
  void println(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
    out('\n');
  }
  void print(long long x) {
    static char s[25], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
  }
  void println(long long x) {
    static char s[25], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
    out('\n');
  }
  void print(double x, int y) {
    static long long mul[] = {1,
                              10,
                              100,
                              1000,
                              10000,
                              100000,
                              1000000,
                              10000000,
                              100000000,
                              1000000000,
                              10000000000LL,
                              100000000000LL,
                              1000000000000LL,
                              10000000000000LL,
                              100000000000000LL,
                              1000000000000000LL,
                              10000000000000000LL,
                              100000000000000000LL};
    if (x < -1e-7) out('-'), x = -x;
    x *= mul[y];
    long long x1 = (long long)floor(x);
    if (x - floor(x) >= 0.5) ++x1;
    long long x2 = x1 / mul[y];
    print(x2);
    if (y > 0) {
      out('.');
      print(x1 - x2 * mul[y]);
    }
  }
  void println(double x, int y) {
    print(x, y);
    out('\n');
  }
  void print(char *s) {
    while (*s) out(*s++);
  }
  void println(char *s) {
    while (*s) out(*s++);
    out('\n');
  }
  void flush() {
    if (p1 != buf) {
      fwrite(buf, 1, p1 - buf, stdout);
      p1 = buf;
    }
  }
  ~Ostream_fwrite() { flush(); }
} Ostream;
inline void print(int x) { Ostream.print(x); }
inline void println(int x) { Ostream.println(x); }
inline void print(char x) { Ostream.out(x); }
inline void println(char x) {
  Ostream.out(x);
  Ostream.out('\n');
}
inline void print(long long x) { Ostream.print(x); }
inline void println(long long x) { Ostream.println(x); }
inline void print(double x, int y) { Ostream.print(x, y); }
inline void println(double x, int y) { Ostream.println(x, y); }
inline void print(char *s) { Ostream.print(s); }
inline void println(char *s) { Ostream.println(s); }
inline void println() { Ostream.out('\n'); }
inline void flush() { Ostream.flush(); }
char Out[100000], *o = Out;
inline void print1(int x) {
  static char buf[15];
  char *p1 = buf;
  if (!x) *p1++ = '0';
  if (x < 0) *o++ = '-', x = -x;
  while (x) *p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf) *o++ = *p1;
}
inline void println1(int x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(long long x) {
  static char buf[25];
  char *p1 = buf;
  if (!x) *p1++ = '0';
  if (x < 0) *o++ = '-', x = -x;
  while (x) *p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf) *o++ = *p1;
}
inline void println1(long long x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(char c) { *o++ = c; }
inline void println1(char c) {
  *o++ = c;
  *o++ = '\n';
}
inline void print1(char *s) {
  while (*s) *o++ = *s++;
}
inline void println1(char *s) {
  print(s);
  *o++ = '\n';
}
inline void println1() { *o++ = '\n'; }
inline void flush1() {
  if (o != Out && *(o - 1) == '\n') *--o = 0;
  puts(Out);
}
struct puts_write {
  ~puts_write() { flush1(); }
};
inline void print2(int x) { printf("%d", x); }
inline void println2(int x) { printf("%d\n", x); }
inline void print2(char x) { printf("%c", x); }
inline void println2(char x) { printf("%c\n", x); }
inline void print2(long long x) { printf("%lld", x); }
inline void println2(long long x) {
  print2(x);
  printf("\n");
}
inline void println2() { printf("\n"); }
};  // namespace fastIO
using namespace fastIO;
string name = "", in = ".in", out = ".out";
const int N = 55;
bool visit[N][N][2][2];
long long f[N][N][2][2];
int a[60], n;
long long k;
long long calc(int l, int r, int f1, int f2) {
  if (l > r) return 1;
  long long &ff = f[l][r][f1][f2];
  if (visit[l][r][f1][f2]) return ff;
  visit[l][r][f1][f2] = 1;
  ff = 0;
  for (int i = 0; i <= 1; i++)
    if (a[l] == -1 || a[l] == i)
      for (int j = 0; j <= 1; j++)
        if (a[r] == -1 || a[r] == j) {
          int _f1 = f1, _f2 = f2;
          if (i < j) _f1 = 1;
          if (i < 1 - j) _f2 = 1;
          if ((l < r || i == j) && (f1 || i <= j) && (f2 || i <= 1 - j))
            ff += calc(l + 1, r - 1, _f1, _f2);
        }
  return ff;
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) a[i] = -1;
  k++;
  if (calc(1, n, 0, 0) < k) {
    printf("-1\n");
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    a[i] = 0;
    memset(visit, 0, sizeof(visit));
    long long p = calc(1, n, 0, 0);
    if (p < k) a[i] = 1, k -= p;
  }
  for (int i = 1; i <= n; i++) printf("%d", a[i]);
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

One Martian boy called Zorg wants to present a string of beads to his friend from the Earth — Masha. He knows that Masha likes two colours: blue and red, — and right in the shop where he has come, there is a variety of adornments with beads of these two colours. All the strings of beads have a small fastener, and if one unfastens it, one might notice that all the strings of beads in the shop are of the same length. Because of the peculiarities of the Martian eyesight, if Zorg sees one blue-and-red string of beads first, and then the other with red beads instead of blue ones, and blue — instead of red, he regards these two strings of beads as identical. In other words, Zorg regards as identical not only those strings of beads that can be derived from each other by the string turnover, but as well those that can be derived from each other by a mutual replacement of colours and/or by the string turnover.

It is known that all Martians are very orderly, and if a Martian sees some amount of objects, he tries to put them in good order. Zorg thinks that a red bead is smaller than a blue one. Let's put 0 for a red bead, and 1 — for a blue one. From two strings the Martian puts earlier the string with a red bead in the i-th position, providing that the second string has a blue bead in the i-th position, and the first two beads i - 1 are identical.

At first Zorg unfastens all the strings of beads, and puts them into small heaps so, that in each heap strings are identical, in his opinion. Then he sorts out the heaps and chooses the minimum string in each heap, in his opinion. He gives the unnecassary strings back to the shop assistant and says he doesn't need them any more. Then Zorg sorts out the remaining strings of beads and buys the string with index k. 

All these manupulations will take Zorg a lot of time, that's why he asks you to help and find the string of beads for Masha.

Input

The input file contains two integers n and k (2 ≤ n ≤ 50;1 ≤ k ≤ 1016) —the length of a string of beads, and the index of the string, chosen by Zorg. 

Output

Output the k-th string of beads, putting 0 for a red bead, and 1 — for a blue one. If it s impossible to find the required string, output the only number -1.

Examples

Input

4 4


Output

0101

Note

Let's consider the example of strings of length 4 — 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110. Zorg will divide them into heaps: {0001, 0111, 1000, 1110}, {0010, 0100, 1011, 1101}, {0011, 1100}, {0101, 1010}, {0110, 1001}. Then he will choose the minimum strings of beads in each heap: 0001, 0010, 0011, 0101, 0110. The forth string — 0101.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int inf = ~0U >> 1;
const long long linf = (long long)1e18;
const double eps = 1e-6;
template <class T>
string tostr(T a) {
  ostringstream out;
  out << a;
  return out.str();
}
struct debugger {
  template <typename T>
  debugger &operator,(const T &x) {
    cerr << x << endl;
    return *this;
  }
} dbg;
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
}
inline void read(long long &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (sign) x = -x;
}
inline void read(double &x) {
  bool sign = 0;
  char ch = nc();
  x = 0;
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  if (ch == '-') sign = 1, ch = nc();
  for (; ch >= '0' && ch <= '9'; ch = nc()) x = x * 10 + ch - '0';
  if (ch == '.') {
    double tmp = 1;
    ch = nc();
    for (; ch >= '0' && ch <= '9'; ch = nc())
      tmp /= 10.0, x += tmp * (ch - '0');
  }
  if (sign) x = -x;
}
inline void read(char *s) {
  char ch = nc();
  for (; blank(ch); ch = nc())
    ;
  if (IOerror) return;
  for (; !blank(ch) && !IOerror; ch = nc()) *s++ = ch;
  *s = 0;
}
inline void read(char &c) {
  for (c = nc(); blank(c); c = nc())
    ;
  if (IOerror) {
    c = -1;
    return;
  }
}
inline void read1(int &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (bo) x = -x;
}
inline void read1(long long &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (bo) x = -x;
}
inline void read1(double &x) {
  char ch;
  int bo = 0;
  x = 0;
  for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') bo = 1;
  for (; ch >= '0' && ch <= '9'; x = x * 10 + ch - '0', ch = getchar())
    ;
  if (ch == '.') {
    double tmp = 1;
    for (ch = getchar(); ch >= '0' && ch <= '9';
         tmp /= 10.0, x += tmp * (ch - '0'), ch = getchar())
      ;
  }
  if (bo) x = -x;
}
inline void read1(char *s) {
  char ch = getchar();
  for (; blank(ch); ch = getchar())
    ;
  for (; !blank(ch); ch = getchar()) *s++ = ch;
  *s = 0;
}
inline void read1(char &c) {
  for (c = getchar(); blank(c); c = getchar())
    ;
}
inline void read2(int &x) { scanf("%d", &x); }
inline void read2(long long &x) { scanf("%lld", &x); }
inline void read2(double &x) { scanf("%lf", &x); }
inline void read2(char *s) { scanf("%s", s); }
inline void read2(char &c) { scanf(" %c", &c); }
inline void readln2(char *s) { gets(s); }
struct Ostream_fwrite {
  char *buf, *p1, *pend;
  Ostream_fwrite() {
    buf = new char[100000];
    p1 = buf;
    pend = buf + 100000;
  }
  void out(char ch) {
    if (p1 == pend) {
      fwrite(buf, 1, 100000, stdout);
      p1 = buf;
    }
    *p1++ = ch;
  }
  void print(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
  }
  void println(int x) {
    static char s[15], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
    out('\n');
  }
  void print(long long x) {
    static char s[25], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
  }
  void println(long long x) {
    static char s[25], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) out('-'), x = -x;
    while (x) *s1++ = x % 10 + '0', x /= 10;
    while (s1-- != s) out(*s1);
    out('\n');
  }
  void print(double x, int y) {
    static long long mul[] = {1,
                              10,
                              100,
                              1000,
                              10000,
                              100000,
                              1000000,
                              10000000,
                              100000000,
                              1000000000,
                              10000000000LL,
                              100000000000LL,
                              1000000000000LL,
                              10000000000000LL,
                              100000000000000LL,
                              1000000000000000LL,
                              10000000000000000LL,
                              100000000000000000LL};
    if (x < -1e-7) out('-'), x = -x;
    x *= mul[y];
    long long x1 = (long long)floor(x);
    if (x - floor(x) >= 0.5) ++x1;
    long long x2 = x1 / mul[y];
    print(x2);
    if (y > 0) {
      out('.');
      print(x1 - x2 * mul[y]);
    }
  }
  void println(double x, int y) {
    print(x, y);
    out('\n');
  }
  void print(char *s) {
    while (*s) out(*s++);
  }
  void println(char *s) {
    while (*s) out(*s++);
    out('\n');
  }
  void flush() {
    if (p1 != buf) {
      fwrite(buf, 1, p1 - buf, stdout);
      p1 = buf;
    }
  }
  ~Ostream_fwrite() { flush(); }
} Ostream;
inline void print(int x) { Ostream.print(x); }
inline void println(int x) { Ostream.println(x); }
inline void print(char x) { Ostream.out(x); }
inline void println(char x) {
  Ostream.out(x);
  Ostream.out('\n');
}
inline void print(long long x) { Ostream.print(x); }
inline void println(long long x) { Ostream.println(x); }
inline void print(double x, int y) { Ostream.print(x, y); }
inline void println(double x, int y) { Ostream.println(x, y); }
inline void print(char *s) { Ostream.print(s); }
inline void println(char *s) { Ostream.println(s); }
inline void println() { Ostream.out('\n'); }
inline void flush() { Ostream.flush(); }
char Out[100000], *o = Out;
inline void print1(int x) {
  static char buf[15];
  char *p1 = buf;
  if (!x) *p1++ = '0';
  if (x < 0) *o++ = '-', x = -x;
  while (x) *p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf) *o++ = *p1;
}
inline void println1(int x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(long long x) {
  static char buf[25];
  char *p1 = buf;
  if (!x) *p1++ = '0';
  if (x < 0) *o++ = '-', x = -x;
  while (x) *p1++ = x % 10 + '0', x /= 10;
  while (p1-- != buf) *o++ = *p1;
}
inline void println1(long long x) {
  print1(x);
  *o++ = '\n';
}
inline void print1(char c) { *o++ = c; }
inline void println1(char c) {
  *o++ = c;
  *o++ = '\n';
}
inline void print1(char *s) {
  while (*s) *o++ = *s++;
}
inline void println1(char *s) {
  print(s);
  *o++ = '\n';
}
inline void println1() { *o++ = '\n'; }
inline void flush1() {
  if (o != Out && *(o - 1) == '\n') *--o = 0;
  puts(Out);
}
struct puts_write {
  ~puts_write() { flush1(); }
};
inline void print2(int x) { printf("%d", x); }
inline void println2(int x) { printf("%d\n", x); }
inline void print2(char x) { printf("%c", x); }
inline void println2(char x) { printf("%c\n", x); }
inline void print2(long long x) { printf("%lld", x); }
inline void println2(long long x) {
  print2(x);
  printf("\n");
}
inline void println2() { printf("\n"); }
};  // namespace fastIO
using namespace fastIO;
string name = "", in = ".in", out = ".out";
const int N = 55;
bool visit[N][N][2][2];
long long f[N][N][2][2];
int a[60], n;
long long k;
long long calc(int l, int r, int f1, int f2) {
  if (l > r) return 1;
  long long &ff = f[l][r][f1][f2];
  if (visit[l][r][f1][f2]) return ff;
  visit[l][r][f1][f2] = 1;
  ff = 0;
  for (int i = 0; i <= 1; i++)
    if (a[l] == -1 || a[l] == i)
      for (int j = 0; j <= 1; j++)
        if (a[r] == -1 || a[r] == j) {
          int _f1 = f1, _f2 = f2;
          if (i < j) _f1 = 1;
          if (i < 1 - j) _f2 = 1;
          if ((l < r || i == j) && (f1 || i <= j) && (f2 || i <= 1 - j))
            ff += calc(l + 1, r - 1, _f1, _f2);
        }
  return ff;
}
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) a[i] = -1;
  k++;
  if (calc(1, n, 0, 0) < k) {
    printf("-1\n");
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    a[i] = 0;
    memset(visit, 0, sizeof(visit));
    long long p = calc(1, n, 0, 0);
    if (p < k) a[i] = 1, k -= p;
  }
  for (int i = 1; i <= n; i++) printf("%d", a[i]);
  return 0;
}

```