„Wenn wir uns jemandem anvertrauen, werden unsere Sorgen schwächer. Die Hälfte der Traurigkeit des Erzählenden geht an sein Gegenüber, die andere Hälfte kehrt mit den Schallwellen in die Welt zurück. So werden die Sorgen unter den Menschen weitergegeben und immer schwächer, bis sie mit dem Wind verschwinden.“

Im kleinen Freundeskreis von 小 I gibt es $n$ Personen. Die Person $i$ ($1\le i\le n$) hat anfangs Sorgen im Umfang der positiven ganzen Zahl $a_i$.

Um die Sorgen aller zu lindern, organisiert 小 I ein Treffen. Dabei sitzen die $n$ Personen in aufsteigender Reihenfolge ihrer Nummern von links nach rechts in einer Reihe.

Die Zeit ist begrenzt, daher kann 小 I während des Treffens höchstens $k$ Gespräche organisieren, in denen sich jemand einem anderen anvertraut. Bei jedem solchen Gespräch vertraut sich eine Person $p$ ($1\le p\le n-1$) ihrem rechten Nachbarn $p+1$ an. Dabei wird zuerst $a_{p+1}\leftarrow a_{p+1}+\frac12a_p$ und anschließend $a_p\leftarrow0$ ausgeführt, wobei $\leftarrow$ eine Zuweisung bezeichnet. 小 I kann die erzählende Person für jedes Gespräch beliebig wählen. Beachte, dass sich die Person mit der Nummer $n$ niemandem anvertraut.

小 I möchte die Sorgen aller möglichst gering halten. Deshalb möchte er wissen: Wie klein kann nach dem Treffen der größte endgültige Sorgenwert aller Personen sein?

Du musst den exakten Wert der Antwort ausgeben. Die Antwort lässt sich stets als $\frac{S}{2^n}$ schreiben, wobei $S$ eine positive ganze Zahl ist, die $2^n\times\left(\max_{i=1}^n a_i\right)$ nicht überschreitet. Gib die Binärdarstellung von $S$ aus.

Eingabe

Lies die Daten aus der Datei confide.in.

Diese Aufgabe enthält mehrere Testfälle. Die erste Eingabezeile enthält eine ganze Zahl $T$, die Anzahl der Testfälle. Anschließend werden die Testfälle der Reihe nach beschrieben.

Für jeden Testfall enthält die erste Zeile zwei ganze Zahlen $n,k$: die Anzahl der Personen und die Höchstzahl der Gespräche. Die zweite Zeile enthält $n$ positive ganze Zahlen $a_1,a_2,\ldots,a_n$, welche die anfänglichen Sorgenwerte der Personen beschreiben.

Ausgabe

Schreibe die Ausgabe in die Datei confide.out.

Gib für jeden Testfall in einer Zeile eine Zeichenkette aus 0 und 1 aus, die die Binärdarstellung von $S$ vom höchstwertigen zum niedrigstwertigen Bit beschreibt. Deine Ausgabe darf keine führenden Nullen enthalten.

Beispiele

Eingabe 1

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

Ausgabe 1

100100
10100
10100

Hinweis

Im ersten Testfall ist es optimal, die erste Person erzählen zu lassen. Die endgültigen Sorgenwerte sind $(0,4.5,1)$. Daher wird die Binärdarstellung von $4.5\times2^3=36$, also 100100, ausgegeben.

Im zweiten und dritten Testfall ist es optimal, zuerst die zweite und dann die erste Person erzählen zu lassen. Die endgültigen Sorgenwerte sind $(0,2.5,2)$. Daher wird die Binärdarstellung von $2.5\times2^3=20$, also 10100, ausgegeben.

Beispiel 2

Siehe confide/confide2.in und confide/confide2.ans im Teilnehmerverzeichnis.

Hinweis

Die Antworten für die sieben Testfälle dieses Beispiels sind der Reihe nach $10,10,8,5,3.5,2.75,2.5$.

Teilaufgaben

Mit $\sum n$ bezeichnen wir die Summe von $n$ über alle Testfälle eines einzelnen Tests. Für alle Testdaten gilt:

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