#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, mod = 1000000007;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acosl(-1.), eps = 1e-9;
inline int power(int a, int b, int m = mod, int ans = 1) {
  for (; b; b >>= 1, a = 1 * a * a % m)
    if (b & 1) ans = 1 * ans * a % m;
  return ans;
}
const int NN = 100000;
char s[NN];
int rk[NN], sa[NN];
namespace SA {
int head[NN * 2];
pair<pair<int, int>, int> pos[NN * 2], buf[NN << 1], tbuf[NN << 1];
int rgt[NN * 2];
void bucket_sort(int ok, int n) {
  int i, u, j, deg, E, K;
  for (i = E = K = 0; i < max(222, n + 10); i++) head[i] = -1;
  for (i = 0; i < n; i++) {
    if (ok)
      u = pos[i].first.first + 1;
    else
      u = pos[i].first.second + 1;
    buf[E] = pos[i];
    rgt[E] = head[u];
    head[u] = E++;
  }
  for (int i = 0; i < max(n + 10, 222); i++) {
    for (deg = 0, j = head[i]; ~j; j = rgt[j]) {
      tbuf[deg++] = buf[j];
    }
    while (deg) pos[K++] = tbuf[--deg];
  }
}
void buildSA(int n) {
  int i, j, cnt, u;
  for (i = 0; i < n; i++) rk[i] = s[i];
  rk[n] = 0;
  for (i = 0; i < 20; i++) {
    for (j = 0; j < n; j++)
      pos[j] = pair<pair<int, int>, int>(
          pair<int, int>(rk[j], rk[min(n, j + (1 << i))]), j);
    bucket_sort(0, n);
    bucket_sort(1, n);
    pos[n] = pair<pair<int, int>, int>(pair<int, int>(-1, -1), -1);
    for (cnt = j = 0; j < n; j++) {
      rk[pos[j].second] = cnt + 1;
      cnt += (pos[j].first != pos[j + 1].first);
    }
    if (cnt == n) break;
  }
  for (int i = 0; i < n; i++) sa[rk[i]] = i;
  ;
}
}  // namespace SA
const int MM = 16;
string a[MM];
int b[MM];
long long cnt[222];
int m;
int n;
long long k;
void ff(string c) {
  string ans;
  for (int i = a[15].size() - c.size();; i--) {
    int flag = 1;
    for (int j = 0; j < c.size(); j++) {
      if (a[15][i + j] != c[j]) {
        flag = 0;
        break;
      }
    }
    k -= flag;
    if (!k) {
      for (int j = i; j < a[15].size() && ans.size() < m; j++) {
        ans += a[15][j];
      }
      cout << ans << endl;
      exit(0);
    }
  }
}
int main() {
  a[0].push_back('0');
  a[1].push_back('1');
  for (int i = 2; i < MM; i++) a[i] = a[i - 2] + a[i - 1];
  cin >> n >> k >> m;
  if (n < MM) {
    int r = a[n].size();
    for (int i = 0; i < r; i++) s[i] = a[n][i];
    SA::buildSA(r);
    s[sa[k] + m] = 0;
    printf("%s\n", s + sa[k]);
    return 0;
  }
  string ans;
  if (k == 1) {
    ans += "01";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  cnt[5] = cnt[6] = 1;
  for (int i = 7; i <= n; i++) {
    cnt[i] = cnt[i - 1] + cnt[i - 2] + (i & 1);
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(55ll, k);
    string c;
    c += "01011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  if (k == 1) {
    ans += "01101";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  if (k == 1) {
    ans += "0110101101";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  cnt[8] = 1;
  cnt[9] = 2;
  for (int i = 10; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(33ll, k);
    string c;
    c += "01101011010";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  cnt[7] = 1;
  cnt[8] = 2;
  for (int i = 9; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(33ll, k);
    string c;
    c += "01101011011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  cnt[6] = cnt[7] = 1;
  for (int i = 8; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1 - (i & 1);
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(55ll, k);
    string c;
    c += "011011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  if (k == 1) {
    ans += "1";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  if (k == 1) {
    ans += "101";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  cnt[5] = cnt[6] = 1;
  for (int i = 7; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + (i & 1);
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(88ll, k);
    string c;
    c += "1010";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  if (k == 1) {
    ans += "101101";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  cnt[6] = 1;
  cnt[7] = 2;
  for (int i = 8; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(88ll, k);
    string c;
    c += "1011010";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  cnt[7] = 1;
  cnt[8] = 2;
  for (int i = 9; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(54ll, k);
    string c;
    c += "1011011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  if (k == 1) {
    ans += "110101101";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  cnt[8] = 1;
  cnt[9] = 2;
  for (int i = 10; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(33ll, k);
    string c;
    c += "1101011010";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  cnt[7] = 1;
  cnt[8] = 2;
  for (int i = 9; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(54ll, k);
    string c;
    c += "1101011011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  cnt[6] = cnt[7] = 1;
  for (int i = 9; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1 - (i & 1);
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(55ll, k);
    string c;
    c += "11011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  return 0;
}

### Prompt

Generate a CPP solution to the following problem:

Let's denote (yet again) the sequence of Fibonacci strings:

F(0) =  0, F(1) =  1, F(i) = F(i - 2) + F(i - 1), where the plus sign denotes the concatenation of two strings.

Let's denote the lexicographically sorted sequence of suffixes of string F(i) as A(F(i)). For example, F(4) is 01101, and A(F(4)) is the following sequence: 01, 01101, 1, 101, 1101. Elements in this sequence are numbered from 1.

Your task is to print m first characters of k-th element of A(F(n)). If there are less than m characters in this suffix, then output the whole suffix.

Input

The only line of the input contains three numbers n, k and m (1 ≤ n, m ≤ 200, 1 ≤ k ≤ 10^{18}) denoting the index of the Fibonacci string you have to consider, the index of the element of A(F(n)) and the number of characters you have to output, respectively.

It is guaranteed that k does not exceed the length of F(n).

Output

Output m first characters of k-th element of A(F(n)), or the whole element if its length is less than m.

Examples

Input

4 5 3


Output

110


Input

4 3 3


Output

1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, mod = 1000000007;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acosl(-1.), eps = 1e-9;
inline int power(int a, int b, int m = mod, int ans = 1) {
  for (; b; b >>= 1, a = 1 * a * a % m)
    if (b & 1) ans = 1 * ans * a % m;
  return ans;
}
const int NN = 100000;
char s[NN];
int rk[NN], sa[NN];
namespace SA {
int head[NN * 2];
pair<pair<int, int>, int> pos[NN * 2], buf[NN << 1], tbuf[NN << 1];
int rgt[NN * 2];
void bucket_sort(int ok, int n) {
  int i, u, j, deg, E, K;
  for (i = E = K = 0; i < max(222, n + 10); i++) head[i] = -1;
  for (i = 0; i < n; i++) {
    if (ok)
      u = pos[i].first.first + 1;
    else
      u = pos[i].first.second + 1;
    buf[E] = pos[i];
    rgt[E] = head[u];
    head[u] = E++;
  }
  for (int i = 0; i < max(n + 10, 222); i++) {
    for (deg = 0, j = head[i]; ~j; j = rgt[j]) {
      tbuf[deg++] = buf[j];
    }
    while (deg) pos[K++] = tbuf[--deg];
  }
}
void buildSA(int n) {
  int i, j, cnt, u;
  for (i = 0; i < n; i++) rk[i] = s[i];
  rk[n] = 0;
  for (i = 0; i < 20; i++) {
    for (j = 0; j < n; j++)
      pos[j] = pair<pair<int, int>, int>(
          pair<int, int>(rk[j], rk[min(n, j + (1 << i))]), j);
    bucket_sort(0, n);
    bucket_sort(1, n);
    pos[n] = pair<pair<int, int>, int>(pair<int, int>(-1, -1), -1);
    for (cnt = j = 0; j < n; j++) {
      rk[pos[j].second] = cnt + 1;
      cnt += (pos[j].first != pos[j + 1].first);
    }
    if (cnt == n) break;
  }
  for (int i = 0; i < n; i++) sa[rk[i]] = i;
  ;
}
}  // namespace SA
const int MM = 16;
string a[MM];
int b[MM];
long long cnt[222];
int m;
int n;
long long k;
void ff(string c) {
  string ans;
  for (int i = a[15].size() - c.size();; i--) {
    int flag = 1;
    for (int j = 0; j < c.size(); j++) {
      if (a[15][i + j] != c[j]) {
        flag = 0;
        break;
      }
    }
    k -= flag;
    if (!k) {
      for (int j = i; j < a[15].size() && ans.size() < m; j++) {
        ans += a[15][j];
      }
      cout << ans << endl;
      exit(0);
    }
  }
}
int main() {
  a[0].push_back('0');
  a[1].push_back('1');
  for (int i = 2; i < MM; i++) a[i] = a[i - 2] + a[i - 1];
  cin >> n >> k >> m;
  if (n < MM) {
    int r = a[n].size();
    for (int i = 0; i < r; i++) s[i] = a[n][i];
    SA::buildSA(r);
    s[sa[k] + m] = 0;
    printf("%s\n", s + sa[k]);
    return 0;
  }
  string ans;
  if (k == 1) {
    ans += "01";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  cnt[5] = cnt[6] = 1;
  for (int i = 7; i <= n; i++) {
    cnt[i] = cnt[i - 1] + cnt[i - 2] + (i & 1);
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(55ll, k);
    string c;
    c += "01011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  if (k == 1) {
    ans += "01101";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  if (k == 1) {
    ans += "0110101101";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  cnt[8] = 1;
  cnt[9] = 2;
  for (int i = 10; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(33ll, k);
    string c;
    c += "01101011010";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  cnt[7] = 1;
  cnt[8] = 2;
  for (int i = 9; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(33ll, k);
    string c;
    c += "01101011011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  cnt[6] = cnt[7] = 1;
  for (int i = 8; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1 - (i & 1);
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(55ll, k);
    string c;
    c += "011011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  if (k == 1) {
    ans += "1";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  if (k == 1) {
    ans += "101";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  cnt[5] = cnt[6] = 1;
  for (int i = 7; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + (i & 1);
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(88ll, k);
    string c;
    c += "1010";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  if (k == 1) {
    ans += "101101";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  cnt[6] = 1;
  cnt[7] = 2;
  for (int i = 8; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(88ll, k);
    string c;
    c += "1011010";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  cnt[7] = 1;
  cnt[8] = 2;
  for (int i = 9; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(54ll, k);
    string c;
    c += "1011011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  if (k == 1) {
    ans += "110101101";
    while (ans.size() > m) ans.pop_back();
    cout << ans << endl;
    return 0;
  } else
    k--;
  cnt[8] = 1;
  cnt[9] = 2;
  for (int i = 10; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(33ll, k);
    string c;
    c += "1101011010";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  cnt[7] = 1;
  cnt[8] = 2;
  for (int i = 9; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1;
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(54ll, k);
    string c;
    c += "1101011011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  cnt[6] = cnt[7] = 1;
  for (int i = 9; i <= n; i++) {
    cnt[i] = cnt[i - 2] + cnt[i - 1] + 1 - (i & 1);
    if (cnt[i] > INF) {
      cnt[n] = INF;
      break;
    }
  }
  if (cnt[n] >= k) {
    k = min(55ll, k);
    string c;
    c += "11011";
    ff(c);
    return 0;
  } else
    k -= cnt[n];
  return 0;
}

```