Problem B
Key Changes

There is no Security through Obscurity. “System security should not depend on the secrecy of the implementation or its components” - National Institute of Standards and Technology (NIST).

Problem

Preface

In a shift cipher of an alphabet of size $N$, a single key (an integer between $0$ and $N-1$) is selected and shared between two parties. To encrypt a plaintext, simply add the value of the key to each character (wrapping around from the end to the beginning of the alphabet as necessary) to get the ciphertext. To decrypt, subtract the value from the ciphertext. This cipher has long been broken by alphabetical frequency distribution attacks. In this problem, you will be helping to decrypt data by finding important details of this unique modified shift cipher.

Scenario

You have been given word that a friend has invented a new encryption scheme based on an adaption of a shift cipher using music being played in a Jazz Club. You have been told that, unlike the shift cipher, there is an added layer of obfuscation! In order to perform the well known frequency distribution attack, you must deobfuscate the ciphertext with a secondary key. The secondary key lies in the musical key of the song being played. The musical key changes often in Jazz, making deobfuscation difficult. You will be tasked with determining when a musical key change happens. This will help deobfuscate the ciphertext based on musical context (but it is not your task to perform a frequency distribution attack on the resulting deobfuscated ciphertext).

Problem Setup

We call the set of all $m$ possible notes that can be played the master set, and represent each note as integer from $0$ to $m-1$. A musical key is a subset of the master set of size $k$. While performing in a certain key, a musician can only play notes from that key. A chord is a set of notes played simultaneously; a chord contains between $3$ and $c$ notes, inclusive. All notes in a chord must be distinct and must respect the current musical key.

Given $m$ and $k$, it is possible to enumerate all possible musical keys. Writing each key as a sorted $k$-tuple of allowed notes, we can sort the keys lexicographically and assign each key a unique integer identifier corresponding to its index in the sorted list. For example, for $m=5$ and $k=4$, key number zero is [0 1 2 3], key $1$ is [0 1 2 4], key $2$ is [0 1 3 4], and so on.

Task

Given a list of chords being played, decide for each chord which key it belongs to, and output the integer that represents this key based on lexicographical ordering as described above. If the key is unable to be determined for a given chord, output a ?.

Since each chord can potentially belong to many possible keys, you will use the following greedy heuristic to help you identify key changes, based on the assumption that in a Jazz composition the key does not change too frequently: when you hear a new chord,

• if you’ve determined the current key (according to the heuristics described here) and the new chord belongs to that key, assume that the key hasn’t changed;

• if you’ve determined the current key, and the new chord doesn’t belong, assume that the key has changed;

• if you are uncertain of the current key, but all of the chords you’ve heard since the last key change could belong to exactly one key, assume all of those chords belong to that same key;

• if you are uncertain of the current key, and all of the chords you’ve heard since the last key change can’t belong to any key, give up on past chords. Treat the key as if it had just changed and start over trying to determine the key with the new chord.

Please refer to the samples for better understanding.

Input

The first line of input contains three integers $m$ ($3 \leq m \leq 25$), $k$ ($3 \leq k \leq m$), and $c$ ($3 \leq c \leq k$ and $c\leq 5$), the size of the master set, the number of notes in a key, and the upper bound on the number of notes in a chord, respectively. The rest of the input contains the chords to be analyzed, one per line. Each chord is given as a sorted tuple of notes, formatted as in the sample input. The input has at most $50$ chords.

Output

Print one integer per chord in the input: the integer identifier of the key to which that chord belongs, according to the rule for detecting key changes described above. Print ? instead if the key cannot be determined.

5 4 3
[0 1 2]
[0 1 3]
[0 1 2]
[0 2 3]
[0 1 4]

0
0
0
0
?

5 4 3
[0 1 2]
[0 1 3]
[0 1 2]
[0 2 3]
[0 1 4]
[0 2 4]

0
0
0
0
1
1

8 6 4
[0 1 2]
[0 1 3 4]
[2 3 4 5]
[0 2 3]
[0 1 2 6]
[0 2 4]
[0 2 4 5]

0
0
0
0
6
6
6

8 6 4
[0 1 2]
[0 1 3 4]
[0 2 3]
[0 1 5 6]
[0 2 4]
[0 2 4 5]

?
?
?
6
6
6