Hit and Blow
Hit and blow — это популярная игра на разгадывание кода, в которую играют два человека: один создатель кода и один разгадыватель. Цель игры — чтобы разгадыватель правильно угадал секретное число, которое создатель держит в уме.
Игра проходит следующим образом. Создатель кода выбирает секретное число, состоящее из четырех различных цифр, включая возможность ведущего нуля. Затем разгадыватель делает первую попытку угадать это число. Угаданное число должно быть допустимым, то есть также состоять из четырех различных цифр. После каждой попытки создатель сообщает разгадывателю количество попаданий и промахов. Попадания — это цифры, которые совпадают и стоят на правильных местах, а промахи — это цифры, которые совпадают, но находятся на других местах. Например, если секретное число 4321, а угаданное 2401, то это одно попадание и два промаха: 1 — это попадание, а 2 и 4 — промахи. После получения этой информации разгадыватель делает следующую попытку. Игра продолжается до тех пор, пока разгадыватель не угадает правильное число.
Ваша задача — написать программу, которая определяет, может ли разгадыватель логически угадать секретное число в течение следующих двух попыток, учитывая текущую ситуацию. Ваша программа получит четырехзначные числа, которые разгадыватель уже угадал, и ответы создателя на эти числа, и должна вывести результат в соответствии со следующими правилами:
если возможно только одно секретное число, выведите это число;
если возможно более одного секретного числа, но есть одно или несколько критических чисел, выведите наименьшее из них;
в противном случае выведите "????" (четыре вопросительных знака).
Критические числа — это такие числа, что после получения количества попаданий и промахов для них в следующей попытке разгадыватель сможет однозначно определить секретное число.
Входные данные
Входные данные состоят из нескольких наборов. Каждый набор представлен в следующем формате:
N
four-digit-number_1 n-hits_1 n-blows_1
...
four-digit-number_N n-hits_N n-blows_N
N — это количество сделанных попыток. four-digit-number_i — это четырехзначное число, угаданное в i-й попытке, а n-hits_i и n-blows_i — это количество попаданий и промахов для этого числа соответственно. Гарантируется, что в каждом наборе данных существует как минимум одно возможное секретное число. Конец ввода обозначается строкой, содержащей ноль. Эту строку обрабатывать не нужно.
Выходные данные
Для каждого набора данных выведите четырехзначное число или "????" в строке в соответствии с указанными выше правилами.