Hide

Problem B
Genetics

Languages de en et is ja lt lv no pl ru sv

For villains that intend to take over the world, a common way to avoid getting caught is to clone themselves. You have managed to catch an evil villain and her N1 clones, and you are now trying to figure out which one of them is the real villain.

To your aid you have each person’s DNA sequence, consisting of M characters, each being either A, C, G or T. You also know that the clones are not perfectly made; rather, their sequences differ in exactly K places compared to the real villain’s.

Can you identify the real villain?

Input

The first line contains the three integers N, M, and K, where 1KM. The following N lines represent the DNA sequences. Each of these lines consists of M characters, each of which is either A, C, G or T.

In the input, there is exactly one sequence that differs from all the other sequences in exactly K places.

Warning: this problem has rather large amounts of input, and will require fast IO in Java.

Output

Output an integer – the index of the DNA sequence that belongs to the villain. The sequences are numbered starting from 1.

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group

Points

Limits

Additional Constraints

1

27

3N,M100

 

2

19

3N,M1800

All characters are either A or C.

3

28

3N,M4100

All characters are either A or C.

4

26

3N,M4100

 
Sample Input 1 Sample Output 1
4 3 1
ACC
CCA
ACA
AAA
3
Sample Input 2 Sample Output 2
4 4 3
CATT
CAAA
ATGA
TCTA
4
Hide

Please log in to submit a solution to this problem

Log in