「在我們傾訴的時候，煩惱衰減了。傾訴者的難過一半交給了對方，另一半隨著聲波還給了世界。煩惱就這樣在人群裡越傳越弱，直到隨風而逝。」

小 I 的小圈子裡有 $n$ 個人，第 $i$（$1\le i\le n$）個人初始有正整數 $a_i$ 的煩惱。

為了減輕大家的煩惱，小 I 組織了一次聊天活動，活動中 $n$ 個人按照編號由小到大的順序，從左到右坐成一排。

時間有限，小 I 可以在活動中組織不超過 $k$ 次傾訴。每次傾訴中，某個傾訴者 $p$（$1\le p\le n-1$）向右手邊的人 $p+1$ 傾訴，這首先導致 $a_{p+1}\leftarrow a_{p+1}+\frac12a_p$，然後 $a_p\leftarrow0$，其中 $\leftarrow$ 表示賦值。小 I 可以任意選擇每次傾訴的傾訴者。注意編號為 $n$ 的人不會向其他人傾訴。

小 I 希望大家的煩惱盡可能少，於是他想知道：在活動過後，所有人最終煩惱的最大值最小是多少。

你需要輸出答案的精確值。具體而言，答案總能寫成 $\frac{S}{2^n}$ 的形式，其中 $S$ 是一個不超過 $2^n\times\left(\max_{i=1}^n a_i\right)$ 的正整數。你需要輸出 $S$ 的二進位表示。

輸入格式

從檔案 confide.in 中讀入資料。

本題有多組測試資料。輸入第一行有一個整數 $T$，表示測試資料組數，接下來依次描述每組測試資料。

對於每組資料，第一行有兩個整數 $n,k$，分別表示人數和傾訴次數上限；第二行有 $n$ 個正整數 $a_1,a_2,\cdots,a_n$，描述初始時每個人的煩惱值。

輸出格式

輸出到檔案 confide.out 中。

對於每組資料，輸出一行一個 01 字串，從高位到低位描述 $S$ 的二進位表示。你的輸出不應有前導零。

範例

輸入格式 1

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

輸出格式 1

100100
10100
10100

說明

對於第一組測試資料，最優策略為讓第一個人傾訴。最終煩惱值為 $(0,4.5,1)$，故輸出 $4.5\times2^3=36$ 的二進位表示 100100。

對於第二和第三組測試資料，最優策略為先讓第二個人傾訴，再讓第一個人傾訴。最終煩惱值為 $(0,2.5,2)$，故輸出 $2.5\times2^3=20$ 的二進位表示 10100。

範例 2

見選手目錄下的 confide/confide2.in 與 confide/confide2.ans。

說明

該組範例七個測試資料的答案分別為 $10,10,8,5,3.5,2.75,2.5$。

子任務

設 $\sum n$ 表示單一測試點中所有測試資料的 $n$ 之和。對於所有測試資料，保證：

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