Hide

Problem G
遺伝学

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

世界を乗っ取ろうとしている悪人にとって、捕まらないようにするための一般的な方法は、 自分自身をクローン化することです。あなたは悪人と$N-1$体のクローンを捕まえることに成功したので、 そのうちのどれが本当の悪人なのかを見極めようとしています。

あなたへのヒントとして、各人のDNAの配列があります。$M$文字で構成されていて、 それぞれの文字はACGTのいずれかです。 また、クローンのDNAは完全に同一ではなく、本物の悪人と比べるとちょうど$K$箇所が異なっています。

本物の悪人を見つけることができますか?

Input

1行目は、$N$, $M$, $K$の3つの整数で、$1 \le K \le M$です。 次の$N$行は、DNAの配列を表します。 これらの行は、それぞれ$M$文字で構成されており、各文字はACGTのいずれかです。

この中に、他のすべての配列と正確に$K$箇所だけ異なる配列が1つだけ存在します。

警告: この問題は入力量がかなり多く、Javaでは高速なIOを必要とします。

Output

悪人のDNA配列が何番目かを整数で出力します。 配列は$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

$3 \le N, M \le 100$

 

2

19

$3 \le N, M \le 1800$

All characters are either A or C.

3

28

$3 \le N, M \le 4100$

All characters are either A or C.

4

26

$3 \le N, M \le 4100$