« Quand nous nous confions, nos soucis s'atténuent. La moitié de la tristesse de celui qui se confie est transmise à l'autre, et l'autre moitié est rendue au monde avec les ondes sonores. Ainsi, les soucis s'affaiblissent en passant de personne en personne, jusqu'à disparaître dans le vent. »

Le petit cercle de 小 I compte $n$ personnes. La personne $i$ ($1\le i\le n$) a initialement une quantité de soucis $a_i$, qui est un entier strictement positif.

Pour alléger les soucis de tous, 小 I organise une discussion. Les $n$ personnes s'assoient en une rangée, de gauche à droite dans l'ordre croissant de leurs numéros.

Le temps est limité : 小 I peut organiser au plus $k$ confidences pendant la discussion. Lors de chaque confidence, une personne $p$ ($1\le p\le n-1$) se confie à son voisin de droite, $p+1$. Cela effectue d'abord $a_{p+1}\leftarrow a_{p+1}+\frac12a_p$, puis $a_p\leftarrow0$, où $\leftarrow$ désigne une affectation. 小 I peut choisir librement la personne qui se confie à chaque fois. Notez que la personne $n$ ne se confie à personne.

小 I souhaite réduire autant que possible les soucis de tous. Il veut donc connaître la plus petite valeur possible du maximum des quantités finales de soucis après la discussion.

Vous devez donner la valeur exacte de la réponse. Plus précisément, la réponse peut toujours s'écrire $\frac{S}{2^n}$, où $S$ est un entier strictement positif ne dépassant pas $2^n\times\left(\max_{i=1}^n a_i\right)$. Vous devez afficher la représentation binaire de $S$.

Entrée

Lisez les données dans le fichier confide.in.

Il y a plusieurs cas de test. La première ligne contient un entier $T$, le nombre de cas. Chaque cas est ensuite décrit successivement.

Pour chaque cas, la première ligne contient deux entiers $n,k$, qui indiquent respectivement le nombre de personnes et le nombre maximal de confidences. La deuxième ligne contient $n$ entiers strictement positifs $a_1,a_2,\ldots,a_n$, les quantités initiales de soucis.

Sortie

Écrivez dans le fichier confide.out.

Pour chaque cas, affichez sur une ligne une chaîne de 0 et de 1 décrivant la représentation binaire de $S$, du bit de poids fort au bit de poids faible. Votre sortie ne doit pas contenir de zéro initial.

Exemples

Entrée 1

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

Sortie 1

100100
10100
10100

Remarque

Pour le premier cas, la stratégie optimale consiste à faire se confier la première personne. Les quantités finales de soucis sont $(0,4.5,1)$. On affiche donc la représentation binaire de $4.5\times2^3=36$, soit 100100.

Pour les deuxième et troisième cas, la stratégie optimale consiste à faire se confier la deuxième personne, puis la première. Les quantités finales de soucis sont $(0,2.5,2)$. On affiche donc la représentation binaire de $2.5\times2^3=20$, soit 10100.

Exemple 2

Consultez confide/confide2.in et confide/confide2.ans dans le répertoire des participants.

Remarque

Les réponses des sept cas de cet exemple sont respectivement $10,10,8,5,3.5,2.75,2.5$.

Sous-tâches

Notons $\sum n$ la somme des valeurs de $n$ de tous les cas d'un même fichier de test. Pour toutes les données, on garantit :

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