«Cuando nos desahogamos, las preocupaciones disminuyen. La mitad de la tristeza de quien se desahoga pasa a la otra persona, y la otra mitad vuelve al mundo con las ondas sonoras. Así, las preocupaciones se transmiten entre la gente cada vez más débiles, hasta desaparecer con el viento».

En el pequeño círculo de 小 I hay $n$ personas. La persona $i$ ($1 \le i \le n$) tiene inicialmente una cantidad de preocupaciones igual al entero positivo $a_i$.

Para aliviar las preocupaciones de todos, 小 I organiza una actividad de conversación, en la que las $n$ personas se sientan en una fila de izquierda a derecha por orden creciente de sus números.

Como el tiempo es limitado, 小 I puede organizar como máximo $k$ desahogos durante la actividad. En cada desahogo, una persona $p$ ($1 \le p \le n-1$) se desahoga con la persona $p+1$, situada a su derecha. Esto produce primero $a_{p+1} \leftarrow a_{p+1}+\frac{1}{2}a_p$ y después $a_p \leftarrow 0$, donde $\leftarrow$ indica una asignación. 小 I puede elegir libremente quién se desahoga en cada ocasión. Ten en cuenta que la persona $n$ no se desahoga con nadie.

小 I desea que todos tengan la menor cantidad posible de preocupaciones, por lo que quiere saber cuál es el mínimo valor posible del máximo de las cantidades finales de preocupaciones de todas las personas después de la actividad.

Debes dar el valor exacto de la respuesta. Concretamente, la respuesta siempre puede escribirse como $\frac{S}{2^n}$, donde $S$ es un entero positivo que no supera $2^n \times (\max_{i=1}^n a_i)$. Debes dar la representación binaria de $S$.

Entrada

Lee los datos del archivo confide.in.

Este problema contiene varios casos de prueba. La primera línea de la entrada contiene un entero $T$, que indica el número de casos de prueba. A continuación se describen sucesivamente todos los casos.

Para cada caso, la primera línea contiene dos enteros $n,k$, que indican, respectivamente, el número de personas y el límite de desahogos. La segunda línea contiene $n$ enteros positivos $a_1,a_2,\ldots,a_n$, que describen la cantidad inicial de preocupaciones de cada persona.

Salida

Escribe la salida en el archivo confide.out.

Para cada caso de prueba, escribe en una línea una cadena de ceros y unos que describa la representación binaria de $S$, del bit más significativo al menos significativo. La salida no debe tener ceros iniciales.

Ejemplos

Entrada 1

3
3 1
5 2 1
3 2
5 2 1
3 3
5 2 1

Salida 1

100100
10100
10100

Nota

Para el primer caso de prueba, la estrategia óptima consiste en que se desahogue la primera persona. Las cantidades finales de preocupaciones son $(0,4.5,1)$, por lo que se escribe 100100, la representación binaria de $4.5\times 2^3=36$.

Para el segundo y el tercer caso de prueba, la estrategia óptima consiste en que primero se desahogue la segunda persona y luego la primera. Las cantidades finales de preocupaciones son $(0,2.5,2)$, por lo que se escribe 10100, la representación binaria de $2.5\times 2^3=20$.

Ejemplo 2

Consulta confide/confide2.in y confide/confide2.ans en el directorio del concursante.

Nota

Las respuestas de los siete casos de prueba de este ejemplo son, respectivamente, $10,10,8,5,3.5,2.75,2.5$.

Subtareas

Sea $\sum n$ la suma de $n$ de todos los casos de prueba de un mismo archivo de pruebas. Para todos los casos de prueba se garantiza lo siguiente:

• $1 \le T \le 2\times 10^4$.
• $1 \le n,\sum n \le 2\times 10^4$, $1 \le k \le 10^9$.
• $\forall 1 \le i \le n$, $1 \le a_i \le 10^6$.