마스터마인드 게임

마스터마인드는 두 사람이 겨루는 고전 논리 게임이다.

한 사람은 P개의 순서 있는 핀으로 이루어진 비밀 코드를 정한다. 각 핀은 미리 정해진 C가지 색 중 하나를 가진다. 어떤 색은 코드에 전혀 나타나지 않을 수도 있고, 어떤 색은 여러 번 나타날 수도 있다.

다른 사람은 이 비밀 코드를 맞혀야 한다. 추측은 비밀 코드와 같은 방식으로 만든 P개의 색 나열이다. 추측할 때마다 상대는 검은 점 B개와 흰 점 W개로 이루어진 힌트를 준다.

• 검은 점: 색과 위치가 모두 맞은 핀마다 하나씩 주어진다.
• 흰 점: 색은 맞았지만 위치가 틀린 핀마다 하나씩 주어진다.

예를 들어 비밀 코드가 (흰색, 노란색, 빨간색, 파란색, 흰색)이고 추측이 (흰색, 빨간색, 흰색, 흰색, 파란색)이라면, 힌트는 검은 점 1개(첫 번째 자리의 흰색)와 흰 점 3개(나머지 흰색, 빨간색, 파란색)로 이루어진다.

이미 진행된 여러 번의 추측과 그 힌트가 주어진다. 지금까지의 모든 힌트와 모순되지 않는(즉 아직 비밀 코드가 될 수 있는) 다음 추측을 만들어라.

첫째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 세 정수 P, C, M이 주어진다.

• P (1 ≤ P ≤ 10): 핀의 개수
• C (1 ≤ C ≤ 100): 색의 개수
• M (1 ≤ M ≤ 100): 이미 진행된 추측의 개수

이어서 진행된 추측마다 두 줄씩, 모두 2·M개의 줄이 주어진다. 각 추측의 첫째 줄에는 추측의 색을 나타내는 P개의 정수 Gᵢ (1 ≤ Gᵢ ≤ C)가, 둘째 줄에는 해당 힌트의 검은 점 수 B와 흰 점 수 W가 주어진다.

엄밀히 말하면, 비밀 코드 S₁ … S_P와 추측 G₁ … G_P에 대해 S_I = G_J를 만족하는 인덱스 쌍 (I, J)들의 집합 H를 생각하자. 단 어느 인덱스도 양쪽에서 두 번 이상 쓰이지 않는다(서로 다른 두 쌍 (I₁, J₁), (I₂, J₂)에 대해 I₁ ≠ I₂ 이고 J₁ ≠ J₂). B(H)를 I = J인 쌍의 수, W(H)를 I ≠ J인 쌍의 수라 하자. 이러한 집합들을 (B(H), W(H))의 사전순으로 정렬했을 때의 최대 집합 H_max에 대해, B(H_max)와 W(H_max)가 그 힌트의 검은 점 수와 흰 점 수이다.

각 테스트 케이스마다 한 줄에 다음 추측의 색 P개를 정수로 출력한다.

이 추측은 이전의 모든 추측과 힌트에 모순되지 않아야 한다. 즉 여전히 비밀 코드가 될 수 있는 코드여야 한다. 조건을 만족하는 코드가 여러 개이면 사전순으로 가장 앞서는 것을 출력한다. 조건을 만족하는 코드가 하나도 없으면 대신 You are cheating!를 출력한다.

(두 코드 A와 B에서, 처음으로 다른 자리에서 A의 색이 더 작으면 A가 사전순으로 더 앞선다.)