31599번 - Personality Test 다국어

문제

There are $n$ students taking a personality test consisting of $m$ questions. The students are numbered from 1ドル$ to $n$ and the questions are numbered from 1ドル$ to $m$. For each question, each student can either answer it with a single uppercase Latin character (A–Z) or not answer it. Let $S_i$ be a string of $m$ characters representing the answers of student $i,ドル where the $j$-th character of $S_i$ is an uppercase Latin character if they answered question $j,ドル or a period (.) if they did not.

Two students are considered similar if there is a set of at least $k$ questions where both students answered all questions in the set, and for each question in the set, they answered it with the same answer.

For example, let $n = 3,ドル $m = 3,ドル $k = 2,ドル $S_1 =$ BBC, $S_2 =$ ..C, and $S_3 =$ .BC. In this example, students 1ドル$ and 3ドル$ are similar since they answered questions 2ドル$ and 3ドル$ with the same answer, while students 2ドル$ and 3ドル$ are not similar since they answered only question 3ドル$ with the same answer.

You want to find a pair of integers $(a, b)$ such that $a < b$ and students $a$ and $b$ are similar, or determine if there is no such pair. If there is more than one pair, find the one with the smallest $b$. If there is still more than one pair, find the one with the largest $a$.

입력

The first line of input contains three integers $n,ドル $m,ドル and $k$ (2ドル ≤ n ≤ 5000$; 1ドル ≤ m ≤ 3000$; 1ドル ≤ k ≤ 5$). Each of the next $n$ lines contains a string of $m$ characters. The $i$-th line contains the string $S_i$.

출력

Output one line containing the integers $a$ and $b$ representing the pair of similar students as mentioned in the problem statement, or just the integer -1 if there is no such pair.

제한

힌트