#include <bits/stdc++.h>
using namespace std;
const int maxn = 210;
long long z1, z2, o1, o2;
int n, m, maxstep;
long long k;
string rez;
void go(int n, long long k, int it) {
  if (z2 >= k || it == n + 1) {
    maxstep = it - 1;
    if (it != n + 1) maxstep++;
    return;
  }
  swap(z1, z2);
  swap(o1, o2);
  o1 += o2;
  z1 += z2;
  go(n, k, it + 1);
}
int zalg(string p, string s) {
  string pom = p + '$' + s;
  int l = 0;
  int r = -1;
  int z[pom.size()];
  memset(z, 0, sizeof(z));
  for (int i = 1; i < pom.size(); i++) {
    if (i > r) {
      l = i;
      r = i - 1;
      while (r + 1 < pom.size() && pom[r + 1] == pom[r - l + 1]) r++;
      z[i] = r - l + 1;
    } else {
      if (i + z[i - l] - 1 >= r) {
        l = i;
        while (r + 1 < pom.size() && pom[r + 1] == pom[r - l + 1]) r++;
        z[i] = r - l + 1;
      } else
        z[i] = z[i - l];
    }
  }
  int ret = 0;
  for (int i = 0; i < pom.size(); i++)
    if (z[i] == p.size()) ret++;
  return ret;
}
long long izbroj(string &s) {
  string prvpref = "0", prvsuff = "0", currpref = "1", currsuff = "1";
  long long cntprv = 0;
  long long cntcurr = 0;
  if (s == prvpref)
    cntprv = 1;
  else if (s == currpref)
    cntcurr = 1;
  if (s.size() == 1) {
    prvpref.clear();
    prvsuff.clear();
    currpref.clear();
    currsuff.clear();
  }
  for (int i = 2; i <= maxstep; i++) {
    string pom1 = currpref;
    string pom2 = currsuff;
    swap(cntprv, cntcurr);
    if (cntcurr > k) return cntcurr;
    cntcurr += cntprv;
    cntcurr += zalg(s, prvsuff + currpref);
    int kolko = s.size() - 1 - currsuff.size();
    string pp;
    for (int j = max(0, (int)prvsuff.size() - kolko); j < prvsuff.size(); j++)
      pp.push_back(prvsuff[j]);
    for (int j = 0; j < currsuff.size(); j++) pp.push_back(currsuff[j]);
    currsuff = pp;
    kolko = s.size() - 1 - prvpref.size();
    for (int j = 0; j < min(kolko, (int)currpref.size()); j++)
      prvpref.push_back(currpref[j]);
    currpref = prvpref;
    prvpref = pom1;
    prvsuff = pom2;
  }
  return cntcurr;
}
long long get_suff(string &s, string &currsuff) {
  string prvpref = "0", prvsuff = "0", currpref = "1";
  currsuff = "1";
  for (int i = 2; i <= maxstep; i++) {
    string pom1 = currpref;
    string pom2 = currsuff;
    int kolko = s.size() - currsuff.size();
    string pp;
    for (int j = max(0, (int)prvsuff.size() - kolko); j < prvsuff.size(); j++)
      pp.push_back(prvsuff[j]);
    for (int j = 0; j < currsuff.size(); j++) pp.push_back(currsuff[j]);
    currsuff = pp;
    kolko = s.size() - prvpref.size();
    for (int j = 0; j < min(kolko, (int)currpref.size()); j++)
      prvpref.push_back(currpref[j]);
    currpref = prvpref;
    prvpref = pom1;
    prvsuff = pom2;
  }
  return 0;
}
bool jeste_sub(string &x) {
  string pom;
  get_suff(x, pom);
  for (int i = x.size() - 1; i >= 0; i--)
    if (x[i] != pom[pom.size() - (x.size() - i)]) return false;
  return true;
}
void build() {
  rez = "";
  for (int i = 0; i < m; i++) {
    rez.push_back('0');
    long long pom = izbroj(rez);
    if (pom < k) {
      rez[rez.size() - 1] = '1';
      k -= pom;
    }
    if (jeste_sub(rez)) k--;
    if (k == 0) break;
  }
}
int main() {
  scanf("%d %lld %d", &n, &k, &m);
  maxstep = min(100, n);
  z1 = 0, z2 = 1, o1 = 1, o2 = 0;
  build();
  cout << rez << endl;
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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 maxn = 210;
long long z1, z2, o1, o2;
int n, m, maxstep;
long long k;
string rez;
void go(int n, long long k, int it) {
  if (z2 >= k || it == n + 1) {
    maxstep = it - 1;
    if (it != n + 1) maxstep++;
    return;
  }
  swap(z1, z2);
  swap(o1, o2);
  o1 += o2;
  z1 += z2;
  go(n, k, it + 1);
}
int zalg(string p, string s) {
  string pom = p + '$' + s;
  int l = 0;
  int r = -1;
  int z[pom.size()];
  memset(z, 0, sizeof(z));
  for (int i = 1; i < pom.size(); i++) {
    if (i > r) {
      l = i;
      r = i - 1;
      while (r + 1 < pom.size() && pom[r + 1] == pom[r - l + 1]) r++;
      z[i] = r - l + 1;
    } else {
      if (i + z[i - l] - 1 >= r) {
        l = i;
        while (r + 1 < pom.size() && pom[r + 1] == pom[r - l + 1]) r++;
        z[i] = r - l + 1;
      } else
        z[i] = z[i - l];
    }
  }
  int ret = 0;
  for (int i = 0; i < pom.size(); i++)
    if (z[i] == p.size()) ret++;
  return ret;
}
long long izbroj(string &s) {
  string prvpref = "0", prvsuff = "0", currpref = "1", currsuff = "1";
  long long cntprv = 0;
  long long cntcurr = 0;
  if (s == prvpref)
    cntprv = 1;
  else if (s == currpref)
    cntcurr = 1;
  if (s.size() == 1) {
    prvpref.clear();
    prvsuff.clear();
    currpref.clear();
    currsuff.clear();
  }
  for (int i = 2; i <= maxstep; i++) {
    string pom1 = currpref;
    string pom2 = currsuff;
    swap(cntprv, cntcurr);
    if (cntcurr > k) return cntcurr;
    cntcurr += cntprv;
    cntcurr += zalg(s, prvsuff + currpref);
    int kolko = s.size() - 1 - currsuff.size();
    string pp;
    for (int j = max(0, (int)prvsuff.size() - kolko); j < prvsuff.size(); j++)
      pp.push_back(prvsuff[j]);
    for (int j = 0; j < currsuff.size(); j++) pp.push_back(currsuff[j]);
    currsuff = pp;
    kolko = s.size() - 1 - prvpref.size();
    for (int j = 0; j < min(kolko, (int)currpref.size()); j++)
      prvpref.push_back(currpref[j]);
    currpref = prvpref;
    prvpref = pom1;
    prvsuff = pom2;
  }
  return cntcurr;
}
long long get_suff(string &s, string &currsuff) {
  string prvpref = "0", prvsuff = "0", currpref = "1";
  currsuff = "1";
  for (int i = 2; i <= maxstep; i++) {
    string pom1 = currpref;
    string pom2 = currsuff;
    int kolko = s.size() - currsuff.size();
    string pp;
    for (int j = max(0, (int)prvsuff.size() - kolko); j < prvsuff.size(); j++)
      pp.push_back(prvsuff[j]);
    for (int j = 0; j < currsuff.size(); j++) pp.push_back(currsuff[j]);
    currsuff = pp;
    kolko = s.size() - prvpref.size();
    for (int j = 0; j < min(kolko, (int)currpref.size()); j++)
      prvpref.push_back(currpref[j]);
    currpref = prvpref;
    prvpref = pom1;
    prvsuff = pom2;
  }
  return 0;
}
bool jeste_sub(string &x) {
  string pom;
  get_suff(x, pom);
  for (int i = x.size() - 1; i >= 0; i--)
    if (x[i] != pom[pom.size() - (x.size() - i)]) return false;
  return true;
}
void build() {
  rez = "";
  for (int i = 0; i < m; i++) {
    rez.push_back('0');
    long long pom = izbroj(rez);
    if (pom < k) {
      rez[rez.size() - 1] = '1';
      k -= pom;
    }
    if (jeste_sub(rez)) k--;
    if (k == 0) break;
  }
}
int main() {
  scanf("%d %lld %d", &n, &k, &m);
  maxstep = min(100, n);
  z1 = 0, z2 = 1, o1 = 1, o2 = 0;
  build();
  cout << rez << endl;
  return 0;
}

```