B - Números k-activos

Time limit: 1 second
Memory limit: 256 megabytes
Languages: MS C# .NET 4.7.2053,GNU G++11 5.1.0 ...

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