“Saat kita mencurahkan isi hati, beban pikiran kita berkurang. Separuh kesedihan orang yang bercerita diberikan kepada lawan bicaranya, sedangkan separuh lainnya dikembalikan kepada dunia melalui gelombang suara. Begitulah beban pikiran makin melemah saat diteruskan dari orang ke orang, hingga akhirnya lenyap terbawa angin.”

Di lingkaran pertemanan kecil Xiao I terdapat $n$ orang. Orang ke-$i$ ($1\le i\le n$) mula-mula memiliki beban pikiran sebesar bilangan bulat positif $a_i$.

Untuk meringankan beban pikiran semua orang, Xiao I mengadakan kegiatan mengobrol. Dalam kegiatan ini, $n$ orang duduk berderet dari kiri ke kanan menurut urutan nomor yang meningkat.

Waktu terbatas, sehingga Xiao I dapat mengadakan paling banyak $k$ kali pencurahan isi hati. Setiap kali, seseorang $p$ ($1\le p\le n-1$) bercerita kepada orang $p+1$ di sebelah kanannya. Pertama dilakukan $a_{p+1}\leftarrow a_{p+1}+\frac12a_p$, lalu $a_p\leftarrow0$, dengan $\leftarrow$ menyatakan penugasan nilai. Xiao I boleh memilih orang yang bercerita pada setiap kesempatan secara bebas. Perhatikan bahwa orang bernomor $n$ tidak akan bercerita kepada orang lain.

Xiao I ingin agar beban pikiran semua orang sekecil mungkin. Ia ingin mengetahui: berapakah nilai minimum yang mungkin dari beban pikiran terbesar di antara semua orang setelah kegiatan tersebut?

Anda harus mengeluarkan nilai jawaban secara tepat. Secara khusus, jawaban selalu dapat ditulis sebagai $\frac{S}{2^n}$, dengan $S$ merupakan bilangan bulat positif yang tidak melebihi $2^n\times(\max_{i=1}^n a_i)$. Anda harus mengeluarkan representasi biner dari $S$.

Masukan

Baca data dari berkas confide.in.

Soal ini memiliki beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$, yaitu banyaknya kasus uji. Selanjutnya setiap kasus uji dijelaskan secara berurutan.

Untuk setiap kasus uji, baris pertama berisi dua bilangan bulat $n,k$, masing-masing menyatakan banyaknya orang dan batas banyaknya pencurahan isi hati; baris kedua berisi $n$ bilangan bulat positif $a_1,a_2,\ldots,a_n$ yang menyatakan beban pikiran awal setiap orang.

Keluaran

Keluarkan hasil ke berkas confide.out.

Untuk setiap kasus uji, keluarkan satu baris berisi sebuah string biner yang menyatakan representasi biner $S$, dari bit paling signifikan ke bit paling tidak signifikan. Keluaran Anda tidak boleh memiliki nol di awal.

Contoh

Masukan 1

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

Keluaran 1

100100
10100
10100

Penjelasan

Untuk kasus uji pertama, strategi optimal adalah meminta orang pertama bercerita. Beban pikiran akhirnya adalah $(0,4.5,1)$, sehingga keluarkan representasi biner $4.5\times2^3=36$, yaitu 100100.

Untuk kasus uji kedua dan ketiga, strategi optimal adalah meminta orang kedua bercerita terlebih dahulu, lalu orang pertama. Beban pikiran akhirnya adalah $(0,2.5,2)$, sehingga keluarkan representasi biner $2.5\times2^3=20$, yaitu 10100.

Contoh 2

Lihat confide/confide2.in dan confide/confide2.ans dalam direktori peserta.

Penjelasan

Jawaban untuk ketujuh kasus uji dalam contoh ini berturut-turut adalah $10,10,8,5,3.5,2.75,2.5$.

Subsoal

Misalkan $\sum n$ menyatakan jumlah $n$ untuk seluruh kasus uji dalam satu berkas pengujian. Untuk semua kasus uji, dijamin:

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