Long long ago, there were n points a1,a2,…,an on the 2D plane. The world keeps stable for a long time. However, it begins to be chaotic recently when another n points b1,b2,…,bn appeared, where bi=ai+(Δx,Δy). And now, these 2n points have already lost their identifiers.
You are given these 2n points in an arbitrary order, you need to figure out all the possible (Δx,Δy) to help the world recover from chaos.
The first line contains a single integer T (1≤T≤100), the number of test cases. For each test case:
The first line of the input contains a single integer n (1≤n≤50,000), denoting the number of initial points.
In the next 2n lines, the i-th line contains two integers xi and yi (∣xi∣,∣yi∣≤1e8), describing the coordinate of a current point.
It is guaranteed that the x-coordinate and y-coordinate of each initial point are chosen uniformly at random from integers in [−v,v], where v is chosen in [1e7,1e8]. The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.
It is also guaranteed that the sum of all n is at most 300,000.
1
3
1 2
3 4
8 9
7 8
6 7
2 32
-5 -5
5 5