Description

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

Farmer John has hidden N (1 <= N <= 20) troughs behind the barn, and has filled some of them with food. Bessie has asked M (1 <= M <= 100) questions of the form, 'How many troughs from this list (which she recites) are filled?'.

Bessie needs your help to deduce which troughs are actually filled.

Consider an example with four troughs where Bessie has asked these questions (and received the indicated answers):

1. 'How many of these troughs are filled: trough 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.

Farmer John and Bessie are playing a game.

Farmer John has prepared $n$ troughs ($1 \le n \le 20$), and some of them contain food. To figure out which troughs contain food, Bessie asks $m$ questions of the form “How many of the troughs numbered $x_1 \cdots x_k$ are filled?” ($1 \le m \le 100$, $1 \le k \le n$).

Please determine which troughs contain food.

Input Format

• 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.

The first line contains two integers $n, m$, denoting the number of troughs and the number of questions, respectively.

Each of the next $m$ lines contains a $01$ string of length $n$ and an integer $t$, where a $1$ in the $01$ string indicates the trough at that position is included in the query, and $t$ is the number of included troughs that are filled.

Output Format

• 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.

If there is no solution, print IMPOSSIBLE.

If there is more than one solution, print NOT UNIQUE.

If there is a unique solution, print a $01$ string in which a $1$ indicates the trough at that position contains food.

4 4 
1000 1 
0110 1 
1001 1 
0011 1 

1010 

Hint

Sample explanation: The four sequences correspond to the following dialogue:

1. Q: How many of the first troughs contain food? — A: $1$.
2. Q: How many of the second and third troughs contain food? — A: $1$.
3. Q: How many of the first and fourth troughs contain food? — A: $1$.
4. Q: How many of the third and fourth troughs contain food? — A: $1$.

From the first question, we can tell the first trough contains food.

From the third question, we can tell the fourth trough does not contain food.

From the fourth question, we can tell the third trough contains food.

From the second question, we can tell the second trough does not contain food.

Translated by ChatGPT 5