“Quando desabafamos, as preocupações diminuem. Metade da tristeza de quem desabafa passa para a outra pessoa, e a outra metade é devolvida ao mundo pelas ondas sonoras. Assim, as preocupações vão enfraquecendo à medida que passam de pessoa para pessoa, até desaparecerem com o vento.”

No pequeno círculo de 小 I há $n$ pessoas. Inicialmente, a $i$-ésima pessoa ($1\le i\le n$) tem uma quantidade de preocupação igual ao inteiro positivo $a_i$.

Para aliviar as preocupações de todos, 小 I organizou uma sessão de conversa, na qual as $n$ pessoas se sentam numa fila, da esquerda para a direita, por ordem crescente dos seus números.

O tempo é limitado, e 小 I pode organizar no máximo $k$ desabafos durante a sessão. Em cada desabafo, uma pessoa $p$ ($1\le p\le n-1$) desabafa com a pessoa $p+1$ à sua direita. Isto provoca primeiro $a_{p+1}\leftarrow a_{p+1}+\frac12a_p$ e depois $a_p\leftarrow0$, onde $\leftarrow$ representa uma atribuição. 小 I pode escolher livremente quem desabafa em cada ocasião. Note que a pessoa de número $n$ não desabafa com ninguém.

小 I quer que todos tenham o mínimo possível de preocupações. Por isso, deseja saber qual é o menor valor possível da maior quantidade final de preocupação entre todas as pessoas, depois da sessão.

Deves apresentar o valor exato da resposta. Mais precisamente, a resposta pode sempre ser escrita na forma $\frac{S}{2^n}$, onde $S$ é um inteiro positivo que não excede $2^n\times(\max_{i=1}^n a_i)$. Deves apresentar a representação binária de $S$.

Entrada

Lê os dados do ficheiro confide.in.

Este problema contém vários casos de teste. A primeira linha contém um inteiro $T$, que indica o número de casos de teste. Seguem-se as descrições de cada caso, pela ordem indicada.

Para cada caso, a primeira linha contém dois inteiros $n,k$, que representam, respetivamente, o número de pessoas e o limite de desabafos; a segunda linha contém $n$ inteiros positivos $a_1,a_2,\cdots,a_n$, que descrevem a quantidade inicial de preocupação de cada pessoa.

Saída

Escreve no ficheiro confide.out.

Para cada caso de teste, apresenta numa linha uma cadeia de zeros e uns que descreva a representação binária de $S$, do bit mais significativo para o menos significativo. A saída não deve ter zeros à esquerda.

Exemplos

Entrada 1

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

Saída 1

100100
10100
10100

Nota

No primeiro caso de teste, a estratégia ótima consiste em deixar a primeira pessoa desabafar. As quantidades finais de preocupação são $(0,4.5,1)$, pelo que se apresenta 100100, a representação binária de $4.5\times2^3=36$.

No segundo e no terceiro casos de teste, a estratégia ótima consiste em deixar primeiro a segunda pessoa desabafar e depois a primeira. As quantidades finais de preocupação são $(0,2.5,2)$, pelo que se apresenta 10100, a representação binária de $2.5\times2^3=20$.

Exemplo 2

Consulta confide/confide2.in e confide/confide2.ans na diretoria do concorrente.

Nota do exemplo 2

As respostas dos sete casos de teste deste exemplo são, respetivamente, $10,10,8,5,3.5,2.75,2.5$.

Subtarefas

Seja $\sum n$ a soma dos valores de $n$ de todos os casos de teste de um único ficheiro de teste. Para todos os casos, garante-se que:

• $1\le T\le2\times10^4$;
• $1\le n,\sum n\le2\times10^4$, $1\le k\le10^9$;
• $\forall1\le i\le n,1\le a_i\le10^6$.