Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 8:00 (UTC) due to technical maintenance. ×

F. Differences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

We have a list of $$$N$$$ strings $$$S_i$$$. All strings have length $$$M$$$ and consist only of characters A, B, C and D. Let us define the distance between two strings $$$X$$$ and $$$Y$$$ as the number of indices $$$j$$$, where the strings have different characters ($$$X_j \neq Y_j$$$). We know that the list of strings $$$S_i$$$ contains precisely one special string that has distance $$$K$$$ to all other strings. Note that there might be other pairs of strings with a distance of $$$K$$$. We are experiencing problems finding this special string, so please write a program to help us out.

Input

The first line contains space-separated integers $$$N$$$, $$$M$$$ and $$$K$$$. Strings $$$S_i$$$ are given in the following $$$N$$$ lines.

Input limits

  • $$$2 \leq N, M \leq 10^5$$$
  • $$$1 \leq K \leq M$$$
  • $$$NM \leq 2 \cdot 10^7$$$
Output

Output the index $$$i$$$ of the special string. Strings are numbered from $$$1$$$ to $$$N$$$ as given in the input.

Examples
Input
5 10 2
DCDDDCCADA
ACADDCCADA
DBADDCCBDC
DBADDCCADA
ABADDCCADC
Output
4
Input
4 6 5
AABAAA
BAABBB
ABAAAA
ABBAAB
Output
2