Genetics

Interview

Time limit2sMemory limit1024 MB

Summary

Given N DNA strings of length M, find the one string that differs from every other string in exactly K positions.

Level: Medium6 of 10
Topics: String, Brute force, Hash map, Implementation
Solved: No attempts yet

Problem

For villains who plot to take over the world, a common way to avoid getting caught is to clone themselves. You have captured an evil villain together with her $N-1$ clones, and you must work out which one of them is the real villain.

To help you, you have the DNA sequence of each person. Each sequence consists of $M$ characters, each of which is one of $A$ , $C$ , $G$ and $T$ . You also know that the clones are imperfect copies: the sequence of each clone differs from the real villain's sequence in exactly $K$ positions.

Can you identify the real villain?

Input

The first line contains three integers $N$ , $M$ and $K$ , where $1 \le K \le M$ . Each of the following $N$ lines holds one DNA sequence, a string of length $M$ consisting only of the letters A, C, G and T.

The input guarantees that exactly one of the sequences differs from every other sequence in exactly $K$ positions.

Note: this problem has a rather large input, so use fast input methods.

Output

Print a single integer, the 1-based index of the DNA sequence that belongs to the real villain.

Examples2

Example 1
Input
```
4 3 1
ACC
CCA
ACA
AAA
```
Expected output
```
3
```
Example 2
Input
```
4 4 3
CATT
CAAA
ATGA
TCTA
```
Expected output
```
4
```