Object detection is a computer vision technique that is used to identify and locate objects in an image. An image can be considered as a 2D array containing rows and columns. Each element at position in the image is called a ‘picture element’ or pixel. In this problem, we will only consider Grayscale Images, which means, each pixel can be described by a single value denoting the intensity (amount of light) of that pixel. Let’s denote a sub-image (where and ) of the image to be a rectangle in the image containing rows and columns.
You will be given an image containing rows and columns, and an object image containing rows and columns . Your task is to find out an sub-image of the given image that has the smallest distance from the object image. To calculate the distance, you need to sum up the squared difference between the intensity of each pixel of the object image and its corresponding pixel in the sub-image. For the sub-image positioned at th row and th column of the original image, we can calculate the distance using:
,
where is the original image and is the object that we are looking for.
The first line of the input contains a single integer , denoting the number of test cases.
The following line contains two space-separated integers and , denoting the number of rows and the number of columns in the original image, respectively. The following lines each contain space-separated integers, describing each pixel’s intensity in the original image.
The next line contains two space-separated integers and , denoting the number of rows and the number of columns in the object image, respectively. The following lines each contain space-separated integers, describing each pixel’s intensity in the object image.
The intensity value of each pixel will be in the range .
Print two space-separated integers denoting the index of the top-left corner of the sub-image that meets the criteria. If there are multiple grids with the smallest distance, print the lexicographically smallest . That means if there are multiple grids that meet the criteria, print the one with the smallest . If there are multiple grids with the smallest that meet the criteria, print the one with the smallest .
Assume that the indices are 1-indexed.
Input | Output |
---|---|
1 3 3 1 2 3 4 4 5 6 7 8 1 1 4 | 2 1 |