#include <bits/stdc++.h>
using namespace std;
template <typename T>
void maxtt(T &t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T &t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 998244353) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 998244353) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
string sf[222], pre[222];
long long dp[222];
int nxt[500];
void Kmp_init(string &str) {
  int k = -1, j = 0;
  nxt[0] = -1;
  int plen = (int)str.size();
  while (j < plen) {
    while (k != -1 && str[k] != str[j]) k = nxt[k];
    nxt[++j] = ++k;
  }
}
int Kmp(string &s, string &p, int C) {
  int j = 0, k = 0, ans = 0, slen = (int)s.size(), plen = (int)p.size();
  while (j < slen) {
    while (k != -1 && s[j] != p[k]) k = nxt[k];
    j++;
    k++;
    if (k == plen) {
      if (j - 1 >= C && j - 1 - (plen - 1) < C) ans++;
      k = nxt[k];
    }
  }
  return ans;
}
long long cal(string ans) {
  if (ans == "") return 0;
  dp[0] = ans == "0" ? 1 : 0;
  dp[1] = ans == "1" ? 1 : 0;
  for (int j = 2; j <= n; j++) {
    dp[j] = dp[j - 2] + dp[j - 1];
    int N = ans.size();
    Kmp_init(ans);
    string tar = sf[j - 2] + pre[j - 1];
    dp[j] += Kmp(tar, ans, (int)sf[j - 2].size());
    mintt(dp[j], (1LL << 60));
  }
  return dp[n];
}
int end(string ans) {
  if (ans == "") return 0;
  int N = ans.size();
  for (int j = sf[n].size() - 1, z = N - 1; j >= 0 && z >= 0; j--, z--) {
    if (sf[n][j] != ans[z]) return 0;
  }
  return 1;
}
void fmain(int tid) {
  scanf("%d%lld%d", &n, &lk, &m);
  sf[0] = pre[0] = "0";
  sf[1] = pre[1] = "1";
  for (int i = 2; i <= n; i++) {
    pre[i] = pre[i - 2] + pre[i - 1];
    while (pre[i].size() > m) pre[i].pop_back();
    sf[i] = sf[i - 2] + sf[i - 1];
    sf[i] = sf[i].substr(max(0, (int)sf[i].size() - m));
  }
  string ans = "";
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    int fd = end(ans);
    if (lk <= fd) break;
    long long a0 = cal(ans + "0");
    if (lk <= a0 + fd) {
      lk -= fd;
      ans += "0";
    } else {
      lk -= a0 + fd;
      ans += "1";
    }
  }
  cout << ans << endl;
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
template <typename T>
void maxtt(T &t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T &t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 998244353) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 998244353) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
string sf[222], pre[222];
long long dp[222];
int nxt[500];
void Kmp_init(string &str) {
  int k = -1, j = 0;
  nxt[0] = -1;
  int plen = (int)str.size();
  while (j < plen) {
    while (k != -1 && str[k] != str[j]) k = nxt[k];
    nxt[++j] = ++k;
  }
}
int Kmp(string &s, string &p, int C) {
  int j = 0, k = 0, ans = 0, slen = (int)s.size(), plen = (int)p.size();
  while (j < slen) {
    while (k != -1 && s[j] != p[k]) k = nxt[k];
    j++;
    k++;
    if (k == plen) {
      if (j - 1 >= C && j - 1 - (plen - 1) < C) ans++;
      k = nxt[k];
    }
  }
  return ans;
}
long long cal(string ans) {
  if (ans == "") return 0;
  dp[0] = ans == "0" ? 1 : 0;
  dp[1] = ans == "1" ? 1 : 0;
  for (int j = 2; j <= n; j++) {
    dp[j] = dp[j - 2] + dp[j - 1];
    int N = ans.size();
    Kmp_init(ans);
    string tar = sf[j - 2] + pre[j - 1];
    dp[j] += Kmp(tar, ans, (int)sf[j - 2].size());
    mintt(dp[j], (1LL << 60));
  }
  return dp[n];
}
int end(string ans) {
  if (ans == "") return 0;
  int N = ans.size();
  for (int j = sf[n].size() - 1, z = N - 1; j >= 0 && z >= 0; j--, z--) {
    if (sf[n][j] != ans[z]) return 0;
  }
  return 1;
}
void fmain(int tid) {
  scanf("%d%lld%d", &n, &lk, &m);
  sf[0] = pre[0] = "0";
  sf[1] = pre[1] = "1";
  for (int i = 2; i <= n; i++) {
    pre[i] = pre[i - 2] + pre[i - 1];
    while (pre[i].size() > m) pre[i].pop_back();
    sf[i] = sf[i - 2] + sf[i - 1];
    sf[i] = sf[i].substr(max(0, (int)sf[i].size() - m));
  }
  string ans = "";
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    int fd = end(ans);
    if (lk <= fd) break;
    long long a0 = cal(ans + "0");
    if (lk <= a0 + fd) {
      lk -= fd;
      ans += "0";
    } else {
      lk -= a0 + fd;
      ans += "1";
    }
  }
  cout << ans << endl;
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}

```