Black Vienna

Time limit1sMemory limit128 MB

Summary
Given each player's hand, the hidden gang, and records of interrogations, find the earliest turn after which at least one player can deduce the gang from their own cards and the answers.
Level

Medium6 of 10

Topics
Brute force, Combinatorics, Simulation, Implementation
Solved
No attempts yet

Problem

This problem is a variant of the board game Black Vienna. Three players use 18 cards labeled with the letters A through R.

  • Three of the cards are set aside and hidden; these three form the gang.
  • The remaining 15 cards are shuffled and dealt so that each player holds 5 cards.
  • Players never reveal their cards to one another.

There is also a separate deck of interrogation cards. Each interrogation card shows three distinct letters in ascending order (for example, ACG or BHR).

Turns rotate through players 1, 2, and 3. On a turn, the active player chooses an interrogation card and places it face up in front of another player. The chosen player must state only how many of the card's three letters they hold, without revealing which ones. For example, if a player is interrogated with ACG and holds A and G but not C, they answer 2. Every player sees the result of the interrogation (who was interrogated, with which card, and the answer).

Each player reasons using only their own 5 cards and every interrogation result revealed so far. From a given player's point of view, that player is certain of the gang once exactly one combination of three gang cards is consistent with everything they know.

Given the records of several games, determine, for each game, the earliest moment at which one or more players can be certain of the gang.

Input

The input consists of one to twelve data sets, followed by a line containing only 0.

Each data set has the following format:

  • The first line contains the number of recorded turns tt (2≤t≤152 \le t \le 15).
  • The second line contains four blank-separated strings: the hands of players 1, 2, and 3 (5 cards each), followed by the 3 gang cards.
  • The next tt lines give the turns in order. Each line contains three blank-separated tokens: the number of the interrogated player, the three interrogation letters, and the answer the interrogated player gave.

Every letter string uses only capital letters from A to R in strictly increasing order. The same interrogation string may appear in more than one turn of a game.

Output

Print one line for each data set. Print the single character ? if no player can be certain of the gang after all recorded turns. Otherwise, print the earliest turn number after which one or more players can be certain of the gang.

Examples4

  1. Example 1

    Input
    9
DGJLP EFOQR ACHMN BIK
2 BJK 0
3 ABK 1
2 DEF 2
2 EIL 1
3 FIP 0
1 GMO 1
2 OQR 3
3 ADQ 1
1 EGJ 2
3
ABCDE FGHIJ KLMNO PQR
3 BKQ 1
1 ADE 3
2 CHJ 2
0
    Expected output
    8
?

  2. Example 2

    Input
    12
ABCDE FGHIJ KLMNO PQR
2 FGH 3
2 HIJ 3
2 FIJ 3
3 KLM 3
3 MNO 3
3 KNO 3
2 FPQ 1
3 LPR 1
2 GIR 2
3 KMQ 2
2 HJP 2
3 LNR 2
0
    Expected output
    5

  3. Example 3

    Input
    2
ABCDE FGHIJ KLMNO PQR
2 PQR 0
3 PQR 0
0
    Expected output
    2

  4. Example 4

    Input
    3
ABCDE FGHIJ KLMNO PQR
2 ABF 1
2 PQR 0
3 PQR 0
0
    Expected output
    3