「私たちが心の内を打ち明けると、悩みは薄れていく。話し手の悲しみの半分は相手に渡され、残りの半分は音の波とともに世界へ返される。悩みはこうして人々の間を伝わるたびに弱まり、やがて風とともに消えていく。」

小 I の仲間は $n$ 人おり、$i$ 番目の人 $(1\le i\le n)$ は最初、正の整数 $a_i$ の悩みを抱えています。

みんなの悩みを軽くするため、小 I はおしゃべりの会を開きました。この会では、$n$ 人が番号の小さい順に左から右へ一列に座ります。

時間が限られているため、小 I が会の中で行える打ち明け話は $k$ 回以下です。1 回の打ち明け話では、話し手 $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\left(\max_{i=1}^{n}a_i\right)$ 以下の正の整数です。$S$ の二進表現を出力してください。

入力

ファイル confide.in から入力を読み込みます。

この問題には複数のテストケースがあります。 入力の最初の行は整数 $T$ で、テストケース数を表します。続いて各テストケースが順に与えられます。

各テストケースの最初の行は 2 つの整数 $n,k$ で、それぞれ人数と打ち明け話の回数の上限を表します。2 行目は $n$ 個の正の整数 $a_1,a_2,\ldots,a_n$ で、各人の最初の悩みの値を表します。

出力

ファイル confide.out に出力してください。

各テストケースについて、$S$ の二進表現を上位ビットから下位ビットの順に表す、0 と 1 からなる文字列を 1 行に出力してください。先頭に余分な 0 を付けてはいけません。

入出力例

入力 1

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

出力 1

100100
10100
10100

注記

最初のテストケースでは、1 番目の人に打ち明け話をさせるのが最適です。最終的な悩みの値は $(0,4.5,1)$ なので、$4.5\times 2^3=36$ の二進表現 100100 を出力します。

2 番目と 3 番目のテストケースでは、まず 2 番目の人に、次に 1 番目の人に打ち明け話をさせるのが最適です。最終的な悩みの値は $(0,2.5,2)$ なので、$2.5\times 2^3=20$ の二進表現 10100 を出力します。

入出力例 2

参加者用ディレクトリの confide/confide2.in と confide/confide2.ans を参照してください。

注記

この入出力例に含まれる 7 個のテストケースの答えは、順に $10,10,8,5,3.5,2.75,2.5$ です。

小課題

$\sum n$ を、1 つの採点用テストに含まれるすべてのテストケースの $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$。