Finding a Constellation

Time limit1sMemory limit128 MB

Summary
Given m constellation points and n photo stars, find the unique translation that moves every constellation point onto a photo star.
Level

Easy3 of 10

Topics
Hash map, Brute force
Solved
No attempts yet

Problem

Sanggeun is looking for a particular constellation in a photo of the night sky. The photo contains exactly one figure that has the same shape, orientation, and size as the constellation he wants to find. However, besides the stars that make up that constellation, the photo also contains other, unrelated stars.

If every star of the target constellation is translated by dxdx along the x-axis and dydy along the y-axis, the result exactly matches the position of the constellation in the photo. (For example, the shift might be 22 in the x-direction and −3-3 in the y-direction.)

Given the shape of the constellation you want to find and the positions of all stars in the photo, write a program that determines the translation (dx,dy)(dx, dy) needed to move the constellation's coordinates onto their positions in the photo. This translation is guaranteed to be unique.

Input

The first line contains the number of stars mm that make up the constellation to find. Each of the next mm lines contains the x- and y-coordinates of one star of the constellation.

The next line contains the number of stars nn in the photo. Each of the next nn lines contains the x- and y-coordinates of one star in the photo.

  • 1≤m≤2001 \le m \le 200
  • 1≤n≤10001 \le n \le 1000
  • All x- and y-coordinates are integers between 00 and 1,000,0001{,}000{,}000, inclusive.

Output

Print, on a single line, the translation that maps the constellation's coordinates onto the photo. The first integer is the shift dxdx along the x-axis and the second integer is the shift dydy along the y-axis, separated by a space.

Examples2

  1. Example 1

    Input
    5
    8 5
    6 4
    4 3
    7 10
    0 10
    10
    10 5
    2 7
    9 7
    8 10
    10 2
    1 2
    8 1
    6 7
    6 0
    0 9
    
    Expected output
    2 -3
    
  2. Example 2

    Input
    5
    904207 809784
    845370 244806
    499091 59863
    638406 182509
    435076 362268
    10
    757559 866424
    114810 239537
    519926 989458
    461089 424480
    674361 448440
    81851 150384
    459107 795405
    299682 6700
    254125 362183
    50795 541942
    
    Expected output
    -384281 179674