10322 - 01串

考虑排好序的N(N<=31)位二进制数。

你会发现,这很有趣。因为他们是排列好的,而且包含所有可能的长度为N且含有1的个数小于等于L(L<=N)的数。

你的任务是输出第I(1<=I<=长度为N的二进制数的个数)大的,长度为N,且含有1的个数小于等于L的那个二进制数。

Input

共一行,用空格分开的三个整数N,L,I。

Output

共一行,输出满足条件的第I大的二进制数。

Examples

Input

5  3  19

Output

10011

Hint

Stringsobits Kim Schrijvers Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.

This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.

Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.

PROGRAM NAME: kimbits INPUT FORMAT A single line with three space separated integers: N, L, and I. SAMPLE INPUT (file kimbits.in) 5 3 19

OUTPUT FORMAT A single line containing the integer that represents the Ith element from the order set, as described. SAMPLE OUTPUT (file kimbits.out) 10011

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题