The Trough Game

Interview

Time limit1sMemory limit128 MB

Summary

Given N troughs and M queries that each count filled troughs within a listed subset, find the filled set or report impossible or non-unique.

Level: Medium6 of 10
Topics: Brute force, Bit manipulation, Math
Solved: No attempts yet

Problem

Farmer John and Bessie are playing another game, this time with troughs of water.

Farmer John has hidden $N$ ( $1 \le N \le 20$ ) troughs behind the barn and filled some of them with food. Bessie asks $M$ ( $1 \le M \le 100$ ) questions, each of the form: “Of the troughs in this list, how many are filled?”

Help Bessie deduce exactly which troughs are filled.

For example, suppose there are four troughs and Bessie asks these four questions, receiving the answers shown:

Troughs {1}: 1 filled
Troughs {2, 3}: 1 filled
Troughs {1, 4}: 1 filled
Troughs {3, 4}: 1 filled

She can reason as follows:

Question 1 says trough 1 is filled.
With trough 1 filled, question 3 forces trough 4 to be empty.
With trough 4 empty, question 4 forces trough 3 to be filled.
With trough 3 filled, question 2 forces trough 2 to be empty.

So the troughs are filled exactly as 1 0 1 0.

Input

Line 1: two space-separated integers $N$ and $M$ .
Lines 2 to $M+1$ : each line describes one question. It is a string of $N$ contiguous characters, each 0 or 1 (a 1 marks a trough that belongs to the question’s list), followed by a space and a single integer giving how many troughs in that list are filled.

Output

Print a single line:

IMPOSSIBLE if no set of filled troughs is consistent with all of Farmer John’s answers.
NOT UNIQUE if the answers are consistent but do not determine the filled troughs uniquely.
Otherwise, a string of $N$ contiguous 0/1 characters giving the unique set of filled troughs.

Examples1

Example 1
Input
```
4 4
1000 1
0110 1
1001 1
0011 1
```
Expected output
```
1010
```