Permutation Puzzle

Indra is thinking of a number with $d$ unique digits, and Josh is trying to guess it.

With every guess Josh makes, Indra will tell him:

• The number of digits in their exact positions, and
• The number of digits still in the number, but at the wrong position.

Josh has made a total of $n$ guesses. Given the feedback Indra has given him, can you help Josh figure out the number?

Do note that Indra will sometimes troll and give hints that will lead to no possible answers!

Input

Your first line will contain two space-separated integers, $n$ and $d$.

Your next $n$ lines will contain three space-separated integers, being, in order:

• Josh's guess of the number,
• The number of digits in their exact positions, and
• The number of digits still in the number, but at the wrong position.

Output

If there is only one possible answer, output the number.

If there are multiple possible answers, output "AMBIGUOUS".

If there is no possible answer, output "IMPOSSIBLE".

Constraints

For all test cases:

• $1 \le d \le 5$
• $1 \le n \le 30$
• The digits in each of Josh's guesses and in Indra's solution are unique.

Example 1

5 3
128 1 0
157 0 1
841 0 2
362 0 0
624 0 1

478

Explanation

Using the first two hints, Josh can determine that the digit $1$ is not in the answer, since the count of exact and misplaced digits would have had overlaps if $1$ were in the answer.

Afterwards, since $1$ is not in the answer, Josh can see with the third hint that both $8$ and $4$ are in the final answer, though not in the positions presented. Combined with the first hint, we can determine that $8$ is in the final position.

Looking at the third hint, we can determine that the $4$ is not in the middle. Looking at the last hint, the $4$ is not in the last spot, either, so the $4$ is at the start.

Back to the second hint where one of them is the correct digit but in the wrong place. The only missing digit is the middle digit, and it cannot be the $5$ in that location. Since it has been established that $1$ is not in the answer, the middle digit must be $7$.

Combining everything above, the solution must be $478$.

Example 2

4 2
12 0 1
34 0 0
56 0 1
78 0 0

AMBIGUOUS

Explanation

In this scenario, there are two possible answers: $25$ or $61$. None of the clues could help us determine which one is correct, so the answer is ambiguous.

Example 3

5 4
6843 0 3
4038 0 2
0821 0 0
5364 2 1
9712 0 0

IMPOSSIBLE

Explanation

The clues given by Indra are contradictory, so there is no possible answer.

Python Template

n, d = map(int, input().split())
josh = list()
for _ in range(n):
    josh.append(map(int, input().split()))