Object Detection

ishtupeed Criterion 2021 Round 14
Limits 1s, 512 MB

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 PP rows and QQ columns. Each element at position (i,j)(i, j) 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 N×MN\times M sub-image (where 1NP1\leq N \leq P and 1MQ1 \leq M \leq Q) of the image to be a rectangle in the image containing NN rows and MM columns.

You will be given an image containing RR rows and CC columns, and an object image containing XX rows and YY columns (XR,YC)(X \leq R, \, Y \leq C). Your task is to find out an X×YX\times Y 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 iith row and jjth column of the original image, we can calculate the distance using:

Distanceij=p=0x1q=0y1(A(i+p)(j+q)B(p+1)(q+1))2\text{Distance}_{ij} = \sum\limits_{p=0}^{x-1}\sum\limits_{q=0}^{y-1}\left(A_{(i+p)(j+q)}-B_{(p+1)(q+1)}\right)^2,

where AA is the original image and BB is the object that we are looking for.

Input

The first line of the input contains a single integer T(1T5)T (1 \leq T \leq 5), denoting the number of test cases.

The following line contains two space-separated integers RR and C(1R,C500)C (1 \leq R, \, C \leq 500), denoting the number of rows and the number of columns in the original image, respectively. The following RR lines each contain CC space-separated integers, describing each pixel’s intensity in the original image.

The next line contains two space-separated integers X(1XR)X (1 \leq X \leq R) and Y(1YC)Y (1 \leq Y \leq C), denoting the number of rows and the number of columns in the object image, respectively. The following XX lines each contain YY space-separated integers, describing each pixel’s intensity in the object image.

The intensity value of each pixel will be in the range [0,50][0, 50].

Output

Print two space-separated integers xyx \, \, y 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 xyx \, \, y. That means if there are multiple grids that meet the criteria, print the one with the smallest xx. If there are multiple grids with the smallest xx that meet the criteria, print the one with the smallest yy.

Assume that the indices are 1-indexed.

Sample

InputOutput
1
3 3
1 2 3
4 4 5
6 7 8
1 1
4
2 1

Submit

Login to submit.

Statistics

50% Solution Ratio
BigBagEarliest, 7M ago
BigBagFastest, 0.4s
BigBagLightest, 14 MB
BigBagShortest, 6777B
Toph uses cookies. By continuing you agree to our Cookie Policy.