当前没有测试数据。

题目背景

IOI 2025 中国国家队选拔 d1t1。

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

100100
10100
10100

输入输出样例 #2

输入 #2

7
10 1
10 9 8 7 6 5 4 3 2 1
10 3
10 9 8 7 6 5 4 3 2 1
10 5
10 9 8 7 6 5 4 3 2 1
10 7
10 9 8 7 6 5 4 3 2 1
10 9
10 9 8 7 6 5 4 3 2 1
10 11
10 9 8 7 6 5 4 3 2 1
10 13
10 9 8 7 6 5 4 3 2 1

输出 #2

10100000000000
10100000000000
10000000000000
1010000000000
111000000000
101100000000
101000000000

说明/提示

样例解释

样例 $1$ 解释

对于第一组测试数据，最优策略为让第一个人倾诉。最终烦恼值为 $(0, 4.5, 1)$，故输出 $4.5 \times 2^3 = 36$ 的二进制表示 $\texttt{100100}$。

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

样例 $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$。

子任务编号	分值	$\sum n\le$	$a_i\le$	$k \ge$
$1$	$2$	$30$	$10^6$	$1$
$2$	$10$	$200$
$3$	$13$	$750$
$4$	$20$	$2,500$
$5$	$17$	$10^4$
$6$	$16$	$2 \times 10^4$	$10^6$	$10^9$
$7$	$22$	$2\times 10^4$		$1$