히트 앤 블로우

히트 앤 블로우는 두 사람이 하는 인기 있는 숫자 맞히기 게임으로, 한 사람은 출제자, 다른 한 사람은 도전자이다. 이 게임의 목표는 도전자가 출제자가 마음속으로 정한 비밀 숫자를 정확히 맞히는 것이다.

게임은 다음과 같이 진행된다. 출제자는 먼저 서로 다른 네 자리 숫자로 이루어진 비밀 숫자를 정한다. 이 숫자는 맨 앞에 0이 올 수 있다. 다음으로 도전자가 비밀 숫자를 처음으로 추측한다. 추측하는 숫자도 서로 다른 네 자리 숫자로 이루어져야 한다. 그러면 출제자는 도전자에게 히트와 블로우의 개수를 알려준다. 히트는 자리까지 맞은 숫자의 개수이고, 블로우는 숫자는 맞지만 자리가 다른 숫자의 개수이다. 예를 들어 비밀 숫자가 4321이고 추측한 숫자가 2401이면 히트가 하나, 블로우가 둘이다. 여기서 1은 히트이고 2와 4는 블로우이다. 답을 들은 도전자는 두 번째 추측을 하고, 출제자는 다시 히트와 블로우의 개수를 알려준다. 그다음 도전자가 세 번째 추측을 하는 식으로 게임이 이어진다. 게임은 도전자가 정확한 숫자를 말하면 끝난다.

이 문제에서 해야 할 일은 주어진 상황에서 도전자가 앞으로 두 번의 추측 안에 비밀 숫자를 논리적으로 알아낼 수 있는지 판단하는 프로그램을 작성하는 것이다. 프로그램에는 도전자가 추측한 네 자리 숫자들과 그 숫자들에 대한 출제자의 응답이 주어지며, 다음 규칙에 따라 출력해야 한다.

• 가능한 비밀 숫자가 하나뿐이면 그 비밀 숫자를 출력한다.
• 가능한 비밀 숫자가 둘 이상이지만 중요한 숫자가 하나 이상 있으면 그중 가장 작은 숫자를 출력한다.
• 그 외의 경우에는 “????”(물음표 네 개)를 출력한다.

여기서 중요한 숫자란, 다음 추측에서 그 숫자에 대한 히트와 블로우의 개수를 들은 뒤 도전자가 비밀 숫자를 하나로 확정할 수 있는 숫자를 말한다.

입력은 여러 개의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.

N
four-digit-number1 n-hits1 n-blows1
...
four-digit-numberN n-hitsN n-blowsN

N은 지금까지 시도한 횟수이다. four-digit-numberi는 i번째 시도에서 추측한 네 자리 숫자이고, n-hitsi와 n-blowsi는 그 숫자에 대한 히트와 블로우의 개수이다. 각 데이터 세트에는 가능한 비밀 숫자가 하나 이상 존재한다.

입력의 끝은 0 하나만 있는 줄로 표시된다. 이 줄은 처리하지 않는다.

각 데이터 세트마다 위 규칙에 따라 네 자리 숫자 또는 “????”를 한 줄에 출력한다.