B - Números k-activos

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Dado tres enteros $M,N,K$ se quiere determinar la M-ésima cadena binaria, en orden lexicográfico, de longitud $N$ y con exactamente $K$ de sus bits activos.

Input

La entrada empieza con un entero $T$ $(1 \leq T \leq 10)$ que indica la cantidad de casos. Cada uno de estos es una línea con los tres enteros $N$ $(1 \leq N \leq 30)$, $K$ $(1 \leq  K \leq N)$ y $M$ $(1 \leq  M \leq 10^{9})$ separados por un espacio.

Output

Por cada caso se debe imprimir el número buscado en una línea. En caso de no existir se debe imprimir $-1$

Sample test(s)

Input
3 3 2 1 3 2 2 3 2 5
Output
011 101 -1