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
#include <bits/stdc++.h>
using namespace std;
const pair<long long, long long> M = make_pair(1e9 + 7, 1e9 + 9);
const long long base = 619;
const int N = 1001;
const long long INF = 2e18 + 7;
pair<long long, long long> operator+(pair<long long, long long> a,
                                     long long x) {
  return make_pair(a.first + x, a.second + x);
}
pair<long long, long long> operator-(pair<long long, long long> a,
                                     long long x) {
  return make_pair(a.first - x, a.second - x);
}
pair<long long, long long> operator*(pair<long long, long long> a,
                                     long long x) {
  return make_pair(a.first * x, a.second * x);
}
pair<long long, long long> operator+(pair<long long, long long> a,
                                     pair<long long, long long> x) {
  return make_pair(a.first + x.first, a.second + x.second);
}
pair<long long, long long> operator-(pair<long long, long long> a,
                                     pair<long long, long long> x) {
  return make_pair(a.first - x.first, a.second - x.second);
}
pair<long long, long long> operator*(pair<long long, long long> a,
                                     pair<long long, long long> x) {
  return make_pair(a.first * x.first, a.second * x.second);
}
pair<long long, long long> operator%(pair<long long, long long> a,
                                     pair<long long, long long> m) {
  return make_pair(a.first % m.first, a.second % m.second);
}
ostream &operator<<(ostream &os, pair<long long, long long> hash) {
  return os << "(" << hash.first << ", " << hash.second << ")";
}
pair<long long, long long> power(pair<long long, long long> a, long long p) {
  if (p == 0) return make_pair(1, 1);
  pair<long long, long long> ans = power(a, p / 2);
  ans = (ans * ans) % M;
  if (p % 2) ans = (ans * a) % M;
  return ans;
}
pair<long long, long long> inverse(pair<long long, long long> a) {
  return power(a, (M.first - 1) * (M.second - 1) - 1);
}
pair<long long, long long> pb[N];
pair<long long, long long> invb;
void hashPre() {
  pb[0] = make_pair(1, 1);
  for (int i = 1; i < N; i++) pb[i] = (pb[i - 1] * base) % M;
  invb = inverse(pb[1]);
}
vector<pair<long long, long long> > hashList(string s) {
  int n = s.size();
  vector<pair<long long, long long> > ans(n + 1);
  ans[0] = make_pair(0, 0);
  for (int i = 1; i <= n; i++) ans[i] = (ans[i - 1] * base + s[i - 1]) % M;
  return ans;
}
pair<long long, long long> substringHash(
    const vector<pair<long long, long long> > &hashlist, int l, int r) {
  int len = (r - l + 1);
  return ((hashlist[r] - hashlist[l - 1] * pb[len]) % M + M) % M;
}
pair<long long, long long> Hash(string s) {
  pair<long long, long long> ans = make_pair(0, 0);
  for (int i = 0; i < s.size(); i++) ans = (ans * base + s[i]) % M;
  return ans;
}
const int K = 15;
int fib[K];
string fibs[K];
vector<pair<long long, long long> > hashes[K];
bool checksuffix(int n, const pair<long long, long long> &h, int k) {
  k = min(k, 14);
  if (fib[k] < n) return false;
  return h == substringHash(hashes[k], fib[k] - n + 1, fib[k]);
}
bool checkprefix(int n, const pair<long long, long long> &h, int k) {
  if (k >= K) k = 14 - k % 2;
  if (fib[k] < n) return false;
  return h == substringHash(hashes[k], 1, n);
}
long long mem[N];
long long count(const vector<pair<long long, long long> > &hl, int k) {
  int n = hl.size() - 1;
  if (k < 2) {
    if (n > 1) return mem[k] = 0;
    return mem[k] = substringHash(hl, 1, 1) == substringHash(hashes[k], 1, 1);
  }
  if (mem[k] >= 0) return mem[k];
  long long left = count(hl, k - 2);
  long long right = count(hl, k - 1);
  long long ans = left + right;
  if (ans >= INF) return mem[k] = INF;
  for (int i = 1; i < n; i++)
    if (checksuffix(i, substringHash(hl, 1, i), k - 2) &&
        checkprefix(n - i, substringHash(hl, i + 1, n), k - 1))
      ans++;
  return mem[k] = min(ans, INF);
}
int main() {
  hashPre();
  fib[0] = 1;
  fib[1] = 1;
  fibs[0] = "0";
  fibs[1] = "1";
  for (int i = 2; i < K; i++) {
    fib[i] = fib[i - 2] + fib[i - 1];
    fibs[i] = fibs[i - 2] + fibs[i - 1];
  }
  for (int i = 0; i < K; i++) hashes[i] = hashList(fibs[i]);
  int m, n;
  long long k;
  cin >> n >> k >> m;
  string ans = "";
  for (int i = 0; i < m; i++) {
    if (i && checksuffix(i, Hash(ans), n)) {
      k--;
      if (k == 0) break;
    }
    memset(mem, -1, sizeof mem);
    long long cnt = count(hashList(ans + "0"), n);
    if (cnt >= k)
      ans += "0";
    else
      ans += "1", k -= cnt;
  }
  cout << ans << endl;
}
