Untitled

You are required to develop a program which searches images.


This program can have up to 10,000 images.


Each image consists of M x M number (3 ≤ M ≤ 10) of pixels, and each pixel has a value of either 0 or 1.


 


Given information about an image to search, this program finds the most similar image to it among the ones that it has.


The most similar image means that the two images share the largest number of matching pixels when they are compared with each other.


 


It is guaranteed that an given image to search has less or equal to 2 unmatched pixels with one of the images owned by the program.


 


You are required to develop a program which fast searches the most similar image among the ones that the program has when an image to search is given.


If the number of the most similar images is two or more, return the one with a smaller ID.


 


The following is the description of API to be written in the User Code.


※ The function signature below is based on C/C++. As for Java, refer to the provided Solution.java and UserSolution.java.


void init(int N, int M, char mImageList[][][])

This function is called once in the beginning of each test case.

 

N is the number of images. The value can be up to 10,000.

M is the size of an image. Each image consists of M x M pixels.

 

mImageList is the data about N number of images owned by the program.

An ID value starts from 1, and each index value of the array is given an ID in order from the smallest to the largest.

For example, an image whose ID is 1 is stored in mImageList[0], and

an image whose ID is 2 in mImageList[1].

Each array of mImageList has a value of either 0 or 1.

 

Parameters
  N : Number of images (10 ≤ N ≤ 10,000)

  M : Size of the image (3 ≤ M ≤ 10)

  mImageList : Information about N number of images

int findImage(char mImage[][])

This function searches N number of existing images, finds the most similar one to an image mImage, and returns its ID.

It is guaranteed that an image to return has less or equal to 2 unmatched pixels with mImage.

If the number of the most similar images is two or more, the one with a smaller ID is returned.

 

This function can be called up to 1,000 times per test case.

 

Parameters
  mImage : Information of images to search

 

Return
  The ID value of the most similar image


 


[Example]


In the first test case, 10 images are given by init(). The information about them is as shown in [Fig. 1].


Each value of the pixels marked with black is 1 while that of the ones marked with white is 0.


 




 


The first image given by findImage() is as shown on the very left in [Fig. 2].


And the pixels marked with red on the right are the ones that are unmatched with the given image.


The images, whose ID is 6, 9, and 10, all have 8 matching pixels. 6 is returned since it is the smallest ID among them.




 


The second image given by findImage() is as shown on the very left in [Fig. 3].


When 10 images are compared with the given image, the one, whose ID is 7, is the most similar image to the given since it has 8 matching pixels. Therefore, this value is returned.




 


That way, findImage() is called 10 times in the first test case.


 


[Constraints]


1. N, the number of images given by init(), is less or equal to 10,000.


2. M, the size of an image, is minimum 3, but no larger than 10.


3. findImage() can be called up to 1,000 times.


 


[Input and Output]


As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code.


 


The output result for the sample input is “#TC number either 100 or 0.” It is the correct answer if the result is 100; it is the wrong answer if it is 0.