“在我们倾诉的时候，烦恼衰减了。倾诉者的难过一半交给了对方，另一半随着声波还给了世界。烦恼就这样在人群里越传越弱，直到随风而逝。”

小 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}+\frac{1}{2}{a}_p$，然后 $a_p\leftarrow 0$，其中 $\leftarrow$ 表示赋值。小 I 可以任意选择每次倾诉的倾诉者。注意编号为 $n$ 的人不会向其他人倾诉。

小 I 希望大家的烦恼尽可能少，于是他想知道：在活动过后，所有人最终烦恼的最大值最小是多少。

你需要输出答案的精确值。具体地，答案总能写成 $\frac{S}{2^n}$ 的形式，其中 $S$ 是一个不超过 $2^n\times (\underset{i=1}{\overset{n}{max}}{a}_i)$ 的正整数。你需要输出 $S$ 的二进制表示。

输入格式

本题有多组测试数据。输入的第一行一个整数 $T$，表示测试数据组数，接下来依次描述每组测试数据。

每组测试数据的第一行两个整数 $n,k$，分别表示人数和倾诉次数上限；第二行 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$ 描述初始每个人的烦恼值。

输出格式

对于每组数据输出一行一个 01 字符串，从高位到低位描述 $S$ 的二进制表示。你的输出不应该有前导零。

样例 #1

样例输入 #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。

对于第二和第三组测试数据，最优策略为先让第二个人倾诉，再让第一个人倾诉。最终烦恼值为 $(0,2.5,2)$，故输出 $2.5\times 2^3=20$ 的二进制表示 10100。

样例 #2

样例输入 #2

见题目目录下的 2.in 与 2.ans。

样例输出 #2

见题目目录下的 2.in 与 2.ans。

【样例 2 解释】

该组样例七个测试数据的答案分别为 $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$，
• $\mathrm{\forall }1\le i\le n,1\le a_i\le {10}^6$。

时间限制：4s $\mathtt{\text{8s}}$

空间限制：$\mathtt{\text{512MB}}$