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;
void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
const long long inf = 1e18 + 19;
const int duzo = 207, maxdl = 200;
int dlug[duzo];
string prefix[duzo], sufix[duzo];
int n, m;
long long k;
long long ile_odp[duzo];
void zrob_prefiksy() {
  prefix[0] = "0";
  prefix[1] = "1";
  sufix[0] = "0";
  sufix[1] = "1";
  for (int i = 2; i <= n; ++i) {
    string rob_pref = prefix[i - 2] + prefix[i - 1];
    string rob_suf = sufix[i - 2] + sufix[i - 1];
    prefix[i] = rob_pref.substr(0, maxdl);
    if ((int)rob_suf.size() > maxdl)
      sufix[i] = rob_suf.substr((int)rob_suf.size() - maxdl, maxdl);
    else
      sufix[i] = rob_suf.substr(0, maxdl);
  }
}
bool rowne(string& sl, int pocz, int dl, string& wz) {
  for (int i = 0; i < dl; ++i)
    if (sl[pocz + i] != wz[i]) return false;
  return true;
}
int licz_wz(string& sl, string& wz) {
  int dl = (int)wz.size();
  int ret = 0;
  for (int i = 0, sss = (int)sl.size(); i < sss; ++i) {
    if (rowne(sl, i, dl, wz)) ++ret;
  }
  return ret;
}
void ile(int nn, string& wz) {
  ile_odp[0] = licz_wz(prefix[0], wz);
  ile_odp[1] = licz_wz(prefix[1], wz);
  for (int i = 2; i <= nn; ++i) {
    long long wyn = ile_odp[i - 1] + ile_odp[i - 2];
    if (wyn >= inf) {
      ile_odp[nn] = inf;
      return;
    }
    string sumacz = sufix[i - 2] + prefix[i - 1];
    long long res = licz_wz(sumacz, wz) - licz_wz(sufix[i - 2], wz) -
                    licz_wz(prefix[i - 1], wz);
    wyn += res;
    if (wyn >= inf) {
      ile_odp[nn] = inf;
      return;
    } else
      ile_odp[i] = wyn;
  }
}
int sprawdz_koniec(string wz) {
  int dl = (int)wz.size();
  if (dl == 0) return 0;
  if (rowne(sufix[n], (int)sufix[n].size() - dl, dl, wz)) return 1;
  return 0;
}
int main() {
  init();
  cin >> n >> k >> m;
  zrob_prefiksy();
  string odp = "";
  ile(n, odp);
  long long ilezzerem;
  long long dodane = 0;
  int czy_koniec;
  for (int i = 1; i <= m; ++i) {
    string odp0 = odp + "0";
    ile(n, odp0);
    ilezzerem = ile_odp[n];
    czy_koniec = sprawdz_koniec(odp);
    if (czy_koniec && dodane + 1 == k) break;
    if (ilezzerem == inf || dodane + ilezzerem + czy_koniec >= k) {
      odp += "0";
      dodane += czy_koniec;
    } else {
      dodane += ilezzerem + czy_koniec;
      odp += "1";
    }
  }
  cout << odp;
  return 0;
}
