Hit and Blow
Hit and blow — це популярна гра на розгадування коду, в яку грають двоє людей: один створює код, а інший намагається його вгадати. Мета гри полягає в тому, щоб той, хто розгадує код, правильно вгадав секретне число, яке задумав той, хто створює код.
Гра проходить наступним чином. Спочатку той, хто створює код, вибирає секретне число, що складається з чотирьох різних цифр, і це число може починатися з нуля. Потім той, хто розгадує код, робить першу спробу вгадати секретне число. Вгадане число має бути легальним (тобто складатися з чотирьох різних цифр). Після цього той, хто створює код, повідомляє кількість влучень і промахів. Влучення — це цифри, які збігаються і стоять на правильних позиціях, а промахи — це цифри, які збігаються, але стоять на різних позиціях. Наприклад, якщо секретне число 4321, а вгадане 2401, то є одне влучення і два промахи, де 1 — це влучення, а 2 і 4 — промахи. Після отримання цієї інформації, той, хто розгадує код, робить другу спробу, і знову отримує кількість влучень і промахів, потім робить третю спробу і так далі. Гра закінчується, коли той, хто розгадує код, вгадує правильне число.
Ваше завдання — написати програму, яка визначає, чи може той, хто розгадує код, логічно вгадати секретне число протягом наступних двох спроб, враховуючи поточну ситуацію. Вашій програмі буде надано чотиризначні числа, які той, хто розгадує код, вже вгадав, і відповіді, які той, хто створює код, дав на ці числа. Програма повинна вивести результат згідно з наступними правилами:
якщо можливе лише одне секретне число, виведіть це секретне число;
якщо можливе більше одного секретного числа, але є одне або більше критичних чисел, виведіть найменше з них;
в іншому випадку, виведіть "????" (чотири знаки питання).
Критичні числа — це такі числа, що після отримання кількості влучень і промахів для них у наступній спробі, той, хто розгадує код, зможе однозначно визначити секретне число.
Вхідні дані
Вхід складається з кількох наборів даних. Кожен набір даних надається у наступному форматі:
N
чотиризначне-число_1 кількість-влучень_1 кількість-промахів_1
...
чотиризначне-число_N кількість-влучень_N кількість-промахів_N
N — це кількість зроблених спроб. чотиризначне-число_i — це чотиризначне число, вгадане під час i-ї спроби, а кількість-влучень_i і кількість-промахів_i — це кількість влучень і промахів для цього числа відповідно. Гарантується, що в кожному наборі даних є принаймні одне можливе секретне число. Кінець вводу позначається рядком, що містить нуль. Цей рядок не слід обробляти.
Вихідні дані
Для кожного набору даних виведіть чотиризначне число або "????" в рядку, згідно з вказаними правилами.