[Usaco2010 Dec]The Trough Game

Farmer John 在谷仓后藏了 $N$ 个食槽，并在其中一些食槽里放入了食物。Bessie 进行了 $M$ 次询问，每次指定若干个食槽，并得知这些食槽中放有食物的食槽数量。

请确定一个长度为 $N$ 的二进制串 $X$，其中第 $j$ 位为 $1$ 表示第 $j$ 个食槽中放有食物，为 $0$ 表示该食槽为空。

对于每次询问，给定一个长度为 $N$ 的二进制串 $B_i$ 和一个整数 $C_i$。$B_i$ 的第 $j$ 位为 $1$ 表示该次询问包含第 $j$ 个食槽。所求的 $X$ 必须满足：

$$\operatorname{popcount}(X\mathbin{\&}B_i)=C_i$$

其中，$\mathbin{\&}$ 表示按位与，$\operatorname{popcount}$ 表示二进制表示中 $1$ 的个数。

如果不存在满足所有询问的状态，需要报告无解；如果存在多个满足条件的状态，需要报告无法唯一确定；否则输出唯一的食槽状态。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $M$，分别表示食槽数量和询问数量。

接下来 $M$ 行，每行包含一个长度为 $N$ 的二进制串 $B_i$ 和一个整数 $C_i$，表示该次询问包含的食槽以及其中放有食物的食槽数量。

输出格式

如果不存在满足所有询问的食槽状态，输出：

IMPOSSIBLE

如果存在多个满足所有询问的食槽状态，输出：

NOT UNIQUE

否则，输出唯一的长度为 $N$ 的二进制串 $X$，表示每个食槽中是否放有食物。

样例输入

4 4
1000 1
0110 1
1001 1
0011 1

样例输出

1010

样例解释

由第 $1$ 次询问可知，第 $1$ 个食槽中放有食物。

结合第 $3$ 次询问可知，第 $4$ 个食槽为空；再结合第 $4$ 次询问可知，第 $3$ 个食槽中放有食物；最后由第 $2$ 次询问可知，第 $2$ 个食槽为空。

因此，唯一可能的食槽状态为 1010。

数据范围

• $1\le N\le 20$；
• $1\le M\le 100$。

来源与许可

本题为 USACO 2010 December 试题「The Trough Game」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 4
1000 1
0110 1
1001 1
0011 1

输出

1010