Under construction

Still being built. Things may change

Picture Comparison

Interview

Time limit2sMemory limit128 MB

Summary
Given N small 5x7 grids, find the pair of pictures with the fewest differing cells and output their indices.
Level

Easy3 of 10

Topics
Brute force, Matrix, Array
Solved
No attempts yet

Problem

There are N pictures (2 <= N <= 50). Each picture has 5 rows and 7 columns, and each cell is represented by either X or ..

The difference between two pictures is the number of positions where their characters are different. Find the two pictures with the smallest difference.

Input

The first line contains N. The next 5 x N lines describe the pictures in input order. Each picture is given by 5 consecutive lines, and each line contains 7 characters.

Output

Print the numbers of the two most similar pictures on one line. Pictures are numbered 1, 2, ..., N in input order. Print the smaller number first. The input is guaranteed to have exactly one answer.

Examples1

  1. Example 1

    Input
    3
..X....
.XXX...
.XX....
.....X.
.X...X.
...X...
..XX...
.XX....
.XX..X.
.X...X.
XX.....
X......
XX...XX
XXXX.XX
XXX..XX
    Expected output
    1 2