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
--- Showing first 30 lines (click "Copy" to get full content) ---
Output
011
101
-1
--- Showing first 30 lines (click "Copy" to get full content) ---