奇怪的背包问题增加了
题号:NC204441
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

有一个容量为的背包,和m件物品,第i件物品的体积为c_i,你需要从中选出若干件,使得选出的物品的体积恰好等于背包容量。这些物品有一个奇怪的特性,那就是,其中,即所有c_i都是2的幂。

输入描述:

第一行,是一个正整数,表示接下来要输入T组测试数据
接下来有T测试数据的输入,对于每组测试数据,输入格式如下:
第一行,一个整数
第二行,用空格隔开的m个非负整数,第i个数字是

输出描述:

依次输出T行,按照输入数据的顺序依次给出每组测试数据的答案,对于一组测试数据:
如果存在一种符合条件的方案,则输出一个长度为m的01串,从前往后的第i位如果是1表示原序列中第i个物品被选中装进背包,为0则表示这个物品不被选中。
如果不存在符合条件的方案,请输出impossible
示例1

输入

复制
2
4
29 1 28 28
7
0 0 1 2 3 4 15

输出

复制
1011
impossible