Genetics

This problem is translated from BalticOI 2018 Day2 "Genetics".

Given N DNA sequences of length M, each composed only of the characters A, T, G, and C and indexed from 1 to N, one of these strings is the pattern string. Every other string differs from the pattern string in exactly K positions. Your task is to find and output the index (1-indexed) of the pattern string.

Note: It is guaranteed that there is exactly one pattern string.

inputFormat

The first line contains three integers: N (number of strings), M (length of each string), and K (the exact number of differences).

Each of the following N lines contains a DNA string of length M composed solely of the characters A, T, G, and C.

outputFormat

Output the index (1-indexed) of the pattern string.

sample

4 5 2
ATGCA
TTGGA
CTCCA
ATACT

1