Indra is thinking of a number with 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 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, and .
Your next 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:
- The digits in each of Josh's guesses and in Indra's solution are unique.
Example 1
Input
5 3
128 1 0
157 0 1
841 0 2
362 0 0
624 0 1
Output
478
Explanation
Using the first two hints, Josh can determine that the digit is not in the answer, since the count of exact and misplaced digits would have had overlaps if were in the answer.
Afterwards, since is not in the answer, Josh can see with the third hint that both and are in the final answer, though not in the positions presented. Combined with the first hint, we can determine that is in the final position.
Looking at the third hint, we can determine that the is not in the middle. Looking at the last hint, the is not in the last spot, either, so the 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 in that location. Since it has been established that is not in the answer, the middle digit must be .
Combining everything above, the solution must be .
Example 2
Input
4 2
12 0 1
34 0 0
56 0 1
78 0 0
Output
AMBIGUOUS
Explanation
In this scenario, there are two possible answers: or . None of the clues could help us determine which one is correct, so the answer is ambiguous.
Example 3
Input
5 4
6843 0 3
4038 0 2
0821 0 0
5364 2 1
9712 0 0
Output
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()))
Comments