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

小 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 (\max_{i=1}^n 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$，
• $\forall 1 \le i \le n, 1 \le a_i \le 10^6$。

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

空间限制：$\texttt{512MB}$