#102102. [BZOJ 2102] [Usaco2010 Dec]The Trough Game

Farmer John and Bessie are playing games again. This one has to do with troughs of water.

Farmer John has hidden N (1 1 trough is filled

2) "How many of these troughs are filled: troughs 2 and 3"
   -->  1 trough is filled

3) "How many of these troughs are filled: troughs 1 and 4"
   -->  1 trough is filled

4) "How many of these troughs are filled: troughs 3 and 4"
   -->  1 trough is filled

From question 1, we know trough 1 is filled. From question 3, we then know trough 4 is empty. From question 4, we then know that trough 3 is filled. From question 2, we then know that trough 2 is empty.

求N位二进制数X，使得给定的M个数，满足X and Bi=Ci ,Bi ci分别是读入的两个数

• Line 1: Two space-separated integers: N and M

• Lines 2..M+1: A subset of troughs, specified as a sequence of contiguous N 0's and 1's, followed by a single integer that is the number of troughs in the specified subset that are filled.

• Line 1: A single line with:

  • The string "IMPOSSIBLE" if there is no possible set of filled troughs compatible with Farmer John's answers.

  • The string "NOT UNIQUE" if Bessie cannot determine from the given data exactly what troughs are filled.

  • Otherwise, a sequence of contiguous N 0's and 1's specifying which troughs are filled.

样例输入

4 4
1000 1
0110 1
1001 1
0011 1

样例输出

1010