„Kiedy zwierzamy się innym, nasze zmartwienia słabną. Połowa smutku osoby, która się zwierza, trafia do rozmówcy, a druga połowa wraz z falami dźwiękowymi wraca do świata. W ten sposób zmartwienia, przekazywane między ludźmi, stają się coraz słabsze, aż w końcu rozwiewa je wiatr”.

W gronie znajomych 小 I jest $n$ osób. Osoba $i$ ($1\le i\le n$) ma początkowo zmartwienie o wartości $a_i$, będącej dodatnią liczbą całkowitą.

Aby zmniejszyć zmartwienia wszystkich osób, 小 I zorganizował spotkanie, podczas którego $n$ osób siada w jednym rzędzie od lewej do prawej w kolejności rosnących numerów.

Czas jest ograniczony, więc 小 I może zorganizować co najwyżej $k$ zwierzeń. Podczas każdego zwierzenia pewna osoba $p$ ($1\le p\le n-1$) zwierza się osobie $p+1$, siedzącej po jej prawej stronie. Najpierw powoduje to $a_{p+1}\leftarrow a_{p+1}+\frac12a_p$, a następnie $a_p\leftarrow0$, gdzie $\leftarrow$ oznacza przypisanie. 小 I może dowolnie wybierać osobę zwierzającą się za każdym razem. Zauważ, że osoba o numerze $n$ nie zwierza się nikomu.

小 I chce, aby wszyscy mieli jak najmniej zmartwień. Chce więc wiedzieć, jaka jest najmniejsza możliwa wartość największego końcowego zmartwienia spośród wszystkich osób po spotkaniu.

Należy wypisać dokładną wartość odpowiedzi. Odpowiedź zawsze można przedstawić w postaci $\frac{S}{2^n}$, gdzie $S$ jest dodatnią liczbą całkowitą nie większą niż $2^n\times\left(\max_{i=1}^{n}a_i\right)$. Należy wypisać zapis binarny liczby $S$.

Wejście

Dane należy wczytać z pliku confide.in.

Dane wejściowe zawierają wiele zestawów testowych. Pierwszy wiersz zawiera liczbę całkowitą $T$, oznaczającą liczbę zestawów testowych. Następnie opisano kolejno każdy zestaw.

W każdym zestawie pierwszy wiersz zawiera dwie liczby całkowite $n,k$, oznaczające odpowiednio liczbę osób i górny limit liczby zwierzeń. Drugi wiersz zawiera $n$ dodatnich liczb całkowitych $a_1,a_2,\ldots,a_n$, opisujących początkowe wartości zmartwień wszystkich osób.

Wyjście

Wyniki należy zapisać do pliku confide.out.

Dla każdego zestawu wypisz w osobnym wierszu ciąg znaków 0 i 1, przedstawiający zapis binarny liczby $S$ od najbardziej do najmniej znaczącego bitu. Wynik nie może zawierać zer wiodących.

Przykład

Wejście 1

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

Wyjście 1

100100
10100
10100

Uwagi

W pierwszym zestawie optymalna strategia polega na tym, by zwierzyła się pierwsza osoba. Końcowe wartości zmartwień wynoszą $(0,4.5,1)$, dlatego wypisujemy zapis binarny liczby $4.5\times2^3=36$, czyli 100100.

W drugim i trzecim zestawie optymalna strategia polega na tym, by najpierw zwierzyła się druga osoba, a następnie pierwsza. Końcowe wartości zmartwień wynoszą $(0,2.5,2)$, dlatego wypisujemy zapis binarny liczby $2.5\times2^3=20$, czyli 10100.

Przykład 2

Zobacz pliki confide/confide2.in i confide/confide2.ans w katalogu zawodnika.

Uwagi do przykładu 2

Odpowiedzi dla siedmiu zestawów w tym przykładzie wynoszą odpowiednio $10,10,8,5,3.5,2.75,2.5$.

Podzadania

Niech $\sum n$ oznacza sumę wartości $n$ we wszystkich zestawach testowych w jednym pliku testowym. Dla wszystkich zestawów testowych gwarantuje się:

• $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$.