校验和

题目描述

一天，brz 在计算机网络的课堂上学习了校验和，就是将一串二进制信息中的 $1$ 的个数作为校验码，将校验码转化成二进制数放在信息的最后作为校验位。 学习到新知识的 brz 迫不及待开始写代码尝试，写完发送方和接收方后，他惊奇的发现明明校验和没有求错，但是接收方校验后发现信息始终有误。 经过仔细的检查后，发现接收方计算校验和时，居然把所有的 $1$，包括校验码中的 $1$ 都算上了，那么自然大概率是不会和发送方发送过来的校验码相同的。 但是 brz 突发奇想，校验码是多少时，能够使得这个接收方校验成功呢？ 具体来说，现在你有一串 $n$ 位的二进制信息 $A$，你需要构造一个 $k$ 位的二进制数 $B$，将 $B$ 接在 $A$ 后面得到要发送的信息 $C$。现在接收方得到了这个 $C$，计算出了其中 $1$ 的个数（二进制下） $D$（保留 $k$ 位二进制，如果有大于 $k$ 位的则舍弃），要使得 $B$与 $D$ 相等。请问 $B$ 是多少。

输入格式

第一行包含一个正整数 $T (1 ≤ T ≤ 2 \times 10^5)$，表示 brz 的问题数量。 对于每个问题，第一行包含两个整数 $n, k (1 ≤ n ≤ 2 \times 10^5, 1 ≤ k ≤ 20)$。第二行包含一个长度为 $n$ 的 $01$ 串 $A$。 保证对于所有的问题，$\sum n ≤ 2 \times 10^5$。

输出格式

每个问题输出一行，表示长度为 $k$ 的合法的 $B$，如果有多个满足要求的答案，则只需要输出最小的 $B$。如果不存在合法的 $B$，则输出一行 "None"（不包含引号）。

样例 #1

样例输入 #1

2
1 1
1
1 2
1

样例输出 #1

None
10

提示

对于样例中第二组数据，$(10)_2,(11)_2$ 都是合法的 B，但是 $(10)_2$ 更小，所以只输出 $10$。