#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
inline void chmin(A &a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A &a, B b) {
  if (a < b) a = b;
}
template <class A, class B>
ostream &operator<<(ostream &ost, const pair<A, B> &p) {
  ost << "{" << p.first << "," << p.second << "}";
  return ost;
}
template <class T>
ostream &operator<<(ostream &ost, const vector<T> &v) {
  ost << "{";
  for (long long i = 0; i < v.size(); i++) {
    if (i) ost << ",";
    ost << v[i];
  }
  ost << "}";
  return ost;
}
template <class T>
vector<long long> zalgorithm(T s) {
  vector<long long> a(s.size());
  a[0] = s.size();
  long long i = 1, j = 0;
  while (i < s.size()) {
    while (i + j < s.size() && s[j] == s[i + j]) j++;
    a[i] = j;
    if (j == 0) {
      i++;
      continue;
    }
    long long k = 1;
    while (i + k < s.size() && k + a[k] < j) a[i + k] = a[k], k++;
    i += k;
    j -= k;
  }
  return a;
}
long long N, K, M;
vector<long long> calcPre(const string &s, const string &p) {
  string X = s + p;
  vector<long long> z = zalgorithm(X);
  vector<long long> a(p.size() + 1);
  for (long long i = 1; i <= p.size(); i++) {
    if (z[X.size() - i] == i) a[i] = 1;
  }
  return a;
}
vector<long long> calcSuf(const string &s, const string &p) {
  string X = p + s;
  vector<long long> z = zalgorithm(X);
  vector<long long> a(p.size() + 1);
  for (long long i = 1; i <= p.size(); i++) {
    if (z[X.size() - i] == i) a[i] = 1;
  }
  return a;
}
long long calcOcc(const string &s, const string &p) {
  string X = p + s;
  vector<long long> z = zalgorithm(X);
  long long ret = 0;
  for (long long i = 0; i < s.size(); i++)
    if (z[p.size() + i] >= p.size()) ret++;
  return ret;
}
long long mrg(const vector<long long> &a, const vector<long long> &b) {
  long long cnt = 0;
  for (long long i = 0; i < a.size(); i++)
    if (a[i] && b[b.size() - 1 - i]) cnt++;
  return cnt;
}
vector<long long> pre[222], suf[222];
long long occ[222];
vector<string> first;
void calc(string s) {
  long long t;
  if (N <= 1) {
    t = 0;
  } else {
    t = 2;
    while (first[t].size() < s.size()) t++;
  }
  for (long long k = 0; k < (2); k++) {
    pre[t + k] = calcPre(first[t + k], s);
    suf[t + k] = calcSuf(first[t + k], s);
    occ[t + k] = calcOcc(first[t + k], s);
    chmin(occ[t + k], K + 1);
  }
  long long BC = mrg(suf[t], pre[t + 1]);
  long long BA = mrg(suf[t], pre[t]);
  for (long long i = t + 2; i <= N; i++) {
    occ[i] = occ[i - 1] + occ[i - 2] + BC;
    chmin(occ[i], K + 1);
    swap(pre[i], pre[i - 2]);
    swap(suf[i], suf[i - 2]);
    swap(BC, BA);
  }
}
signed main() {
  first.push_back("0");
  first.push_back("1");
  while (first.back().size() < 10000) {
    first.push_back(first[first.size() - 2] + first[first.size() - 1]);
  }
  cin >> N >> K >> M;
  K--;
  string ans;
  for (long long i = 0; i < M; i++) {
    if (i) {
      if (suf[N][ans.size()]) {
        if (K == 0) break;
        K--;
      }
    }
    calc(ans + "0");
    long long tmp = occ[N];
    if (tmp <= K) {
      K -= tmp;
      ans += "1";
      calc(ans);
    } else {
      ans += "0";
    }
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Your task is to create 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;
template <typename A, typename B>
inline void chmin(A &a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A &a, B b) {
  if (a < b) a = b;
}
template <class A, class B>
ostream &operator<<(ostream &ost, const pair<A, B> &p) {
  ost << "{" << p.first << "," << p.second << "}";
  return ost;
}
template <class T>
ostream &operator<<(ostream &ost, const vector<T> &v) {
  ost << "{";
  for (long long i = 0; i < v.size(); i++) {
    if (i) ost << ",";
    ost << v[i];
  }
  ost << "}";
  return ost;
}
template <class T>
vector<long long> zalgorithm(T s) {
  vector<long long> a(s.size());
  a[0] = s.size();
  long long i = 1, j = 0;
  while (i < s.size()) {
    while (i + j < s.size() && s[j] == s[i + j]) j++;
    a[i] = j;
    if (j == 0) {
      i++;
      continue;
    }
    long long k = 1;
    while (i + k < s.size() && k + a[k] < j) a[i + k] = a[k], k++;
    i += k;
    j -= k;
  }
  return a;
}
long long N, K, M;
vector<long long> calcPre(const string &s, const string &p) {
  string X = s + p;
  vector<long long> z = zalgorithm(X);
  vector<long long> a(p.size() + 1);
  for (long long i = 1; i <= p.size(); i++) {
    if (z[X.size() - i] == i) a[i] = 1;
  }
  return a;
}
vector<long long> calcSuf(const string &s, const string &p) {
  string X = p + s;
  vector<long long> z = zalgorithm(X);
  vector<long long> a(p.size() + 1);
  for (long long i = 1; i <= p.size(); i++) {
    if (z[X.size() - i] == i) a[i] = 1;
  }
  return a;
}
long long calcOcc(const string &s, const string &p) {
  string X = p + s;
  vector<long long> z = zalgorithm(X);
  long long ret = 0;
  for (long long i = 0; i < s.size(); i++)
    if (z[p.size() + i] >= p.size()) ret++;
  return ret;
}
long long mrg(const vector<long long> &a, const vector<long long> &b) {
  long long cnt = 0;
  for (long long i = 0; i < a.size(); i++)
    if (a[i] && b[b.size() - 1 - i]) cnt++;
  return cnt;
}
vector<long long> pre[222], suf[222];
long long occ[222];
vector<string> first;
void calc(string s) {
  long long t;
  if (N <= 1) {
    t = 0;
  } else {
    t = 2;
    while (first[t].size() < s.size()) t++;
  }
  for (long long k = 0; k < (2); k++) {
    pre[t + k] = calcPre(first[t + k], s);
    suf[t + k] = calcSuf(first[t + k], s);
    occ[t + k] = calcOcc(first[t + k], s);
    chmin(occ[t + k], K + 1);
  }
  long long BC = mrg(suf[t], pre[t + 1]);
  long long BA = mrg(suf[t], pre[t]);
  for (long long i = t + 2; i <= N; i++) {
    occ[i] = occ[i - 1] + occ[i - 2] + BC;
    chmin(occ[i], K + 1);
    swap(pre[i], pre[i - 2]);
    swap(suf[i], suf[i - 2]);
    swap(BC, BA);
  }
}
signed main() {
  first.push_back("0");
  first.push_back("1");
  while (first.back().size() < 10000) {
    first.push_back(first[first.size() - 2] + first[first.size() - 1]);
  }
  cin >> N >> K >> M;
  K--;
  string ans;
  for (long long i = 0; i < M; i++) {
    if (i) {
      if (suf[N][ans.size()]) {
        if (K == 0) break;
        K--;
      }
    }
    calc(ans + "0");
    long long tmp = occ[N];
    if (tmp <= K) {
      K -= tmp;
      ans += "1";
      calc(ans);
    } else {
      ans += "0";
    }
  }
  cout << ans << endl;
  return 0;
}

```