「當我哋傾訴嗰陣，煩惱就減輕咗。傾訴者嘅難過有一半交咗畀對方，另一半就隨住聲波交返畀世界。煩惱就係咁喺人群之間越傳越弱，直到隨風消逝。」

小 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}+\frac12 a_p$，然後令 $a_p\leftarrow 0$，當中 $\leftarrow$ 代表賦值。小 I 可以任意揀每次傾訴嘅傾訴者。留意編號為 $n$ 嘅人唔會向其他人傾訴。

小 I 希望大家嘅煩惱盡可能少，所以佢想知：活動結束之後，所有人最終煩惱嘅最大值，最細可以係幾多。

你要輸出答案嘅精確值。具體嚟講，答案一定可以寫成 $\frac{S}{2^n}$，當中 $S$ 係一個唔超過 $2^n\times(\max_{i=1}^n a_i)$ 嘅正整數。你要輸出 $S$ 嘅二進制表示。

輸入格式

由檔案 confide.in 讀入資料。

呢題有多組測試資料。 輸入第一行有一個整數 $T$，代表測試資料組數，之後依次描述每組測試資料。

每組資料第一行有兩個整數 $n,k$，分別代表人數同傾訴次數上限；第二行有 $n$ 個正整數 $a_1,a_2,\ldots,a_n$，描述每個人最初嘅煩惱值。

輸出格式

輸出至檔案 confide.out。

每組資料輸出一行，一個由 0 同 1 組成嘅字串，由高位到低位描述 $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\times 2^3=36$ 嘅二進制表示 100100。

第二同第三組測試資料嘅最優策略係先畀第二個人傾訴，再畀第一個人傾訴。最終煩惱值係 $(0,2.5,2)$，所以輸出 $2.5\times 2^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\le 2\times 10^4$；
• $1\le n,\sum n\le 2\times 10^4$，$1\le k\le 10^9$；
• $\forall 1\le i\le n,1\le a_i\le 10^6$。