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 int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const long long MAX = static_cast<long long>(2e18);
const int MAXN = 1007;
const int L = 12;
int n, m;
long long K;
string s[L + 3], s0, s1;
int fail[MAXN];
bool inl[MAXN], inr[MAXN];
void init();
void input();
void work();
long long getcc(string s);
int kmp(string s, string t);
int getintersect(string sl, string sr, string s);
void getborder(string s, string t, bool in[]);
int main() {
  init();
  input();
  work();
}
void init() { ios::sync_with_stdio(false); }
void input() { cin >> n >> K >> m; }
void work() {
  s[0] = "0", s[1] = "1";
  for (int i = 2; i <= L + 2; ++i) s[i] = s[i - 2] + s[i - 1];
  s0 = s[L], s1 = s[L + 1];
  string ans = "", tmp, rs = (n <= L + 1) ? s[n] : s1;
  long long cc, rem = K;
  for (int i = 0; i < m; ++i) {
    if (i && rs.substr(rs.size() - i) == ans) {
      if (rem == 1)
        break;
      else
        --rem;
    }
    tmp = ans + "0";
    cc = getcc(tmp);
    if (rem <= cc)
      ans = tmp;
    else
      ans += "1", rem -= cc;
  }
  cout << ans << endl;
}
long long getcc(string s) {
  if (n <= L + 1) return kmp(::s[n], s);
  long long c0 = kmp(s0, s), c1 = kmp(s1, s), ct;
  int cl = 1, i10 = getintersect(s1, s0, s), i11 = getintersect(s1, s1, s);
  for (int i = L + 2; i <= n; ++i) {
    ct = (((c0 + c1 + (cl ? i11 : i10)) < (MAX)) ? (c0 + c1 + (cl ? i11 : i10))
                                                 : (MAX));
    c0 = c1, c1 = ct;
    cl ^= 1;
  }
  return c1;
}
int kmp(string s, string t) {
  int n = s.size(), m = t.size();
  t += '$';
  fail[0] = -1;
  int f = 0;
  for (int i = 1; i <= m; ++i) {
    fail[i] = f;
    if (t[i] == t[fail[i]]) fail[i] = fail[fail[i]];
    while ((~f) && t[i] != t[f]) f = fail[f];
    ++f;
  }
  int ans = 0, cur = 0;
  for (int i = 0; i < n; ++i) {
    while ((~cur) && (s[i] != t[cur])) cur = fail[cur];
    ++cur;
    if (cur == m) ++ans;
  }
  return ans;
}
int getintersect(string sl, string sr, string s) {
  memset(inl, false, sizeof(inl));
  memset(inr, false, sizeof(inr));
  int n = s.size();
  getborder(s, sl.substr(sl.size() - n), inl);
  getborder(sr.substr(0, n), s, inr);
  int ans = 0;
  for (int i = 1; i < n; ++i)
    if (inl[i] && inr[n - i]) ++ans;
  return ans;
}
void getborder(string s, string t, bool in[]) {
  int n = s.size(), m = n << 1;
  t = s + t;
  t += '$';
  fail[0] = -1;
  int f = 0;
  for (int i = 1; i <= m; ++i) {
    fail[i] = f;
    while ((~f) && t[i] != s[f]) f = fail[f];
    ++f;
  }
  for (int t = fail[m]; ~t; t = fail[t])
    if (t < n) in[t] = true;
}
