D. Disinfection Patch
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

A hospital in some city has been researching technology which can completely revolutionize the current remedial methods. For this purpose, the simulation was created to evaluate the cost.

There is a disinfection patch with coordinate $$$(0,0)$$$ as the center of the patch. The $$$N$$$ drops of disinfection substances will be applied on the patch coordinate $$$(x_i,y_i)$$$. The $$$N$$$ types of bacteria have also been placed on coordinate $$$(a_i,b_i)$$$. All of the substances can disinfect any type of bacteria, but can only disinfect 1 type of bacteria per drop, and only disinfect at the point that the substances reside.

The disinfection patch can also be stretched out with the same non-negative integer $$$S$$$ both horizontally and vertically and can't be rotated or flipped. After that, the disinfection patch center can also be placed on any integer coordinates. The disinfection substances coordinate will also be changed as follows.

1. If the original coordinate for substance is $$$(p,q)$$$, then the new substance coordinate is $$$(S\cdot p,S\cdot q)$$$.

2. Assume that the center of the patch is $$$(X,Y)$$$, then the new substance coordinate is $$$(S\cdot p+X,S\cdot q+Y)$$$.

To simulate real-life situations for reducing cost, only one disinfection patch was given to you. Your task is to determine the value of $$$S,X,Y$$$ that can disinfect all of the bacteria for each simulation.

Input

The first line contains two integers $$$N$$$ $$$(1 \leq N \leq 2,000)$$$ — the number of drops of disinfection substances.

The $$$i^{th}$$$ line of the following $$$N$$$ lines contains integer $$$x_i,y_i$$$ $$$(|x_i|,|y_i| \leq 10^9)$$$ — the coordinate of the $$$i^{th}$$$ drop of disinfection substance.

The $$$i^{th}$$$ line of the following $$$N$$$ lines contains integer $$$a_i,b_i$$$ $$$(|a_i|,|b_i| \leq 10^9)$$$ — the coordinate of the $$$i^{th}$$$ type of bacteria.

Output

The first line contains an integer $$$S,X,Y$$$, the stretched out scale with value in range $$$[0,2\cdot 10^9]$$$, and the center coordinate for the disinfection patch with $$$X$$$ and $$$Y$$$ in range $$$[-4\cdot 10^{18},4\cdot 10^{18}]$$$. If there are multiple solutions, output any of them.

If there is no plausible solution, output $$$-1$$$ for the line.

Examples
Input
5
1 1
2 2
3 3
4 4
5 5
4 5
7 8
10 11
16 17
13 14
Output
3 1 2
Input
5
1 1
2 2
3 3
4 4
5 5
-1 1
-2 2
-3 3
-4 4
-5 5
Output
-1
Input
5
-1 1
0 1
1 1
-1 0
1 0
-10 -17
-7 -17
-7 -20
-13 -20
-13 -17
Output
3 -10 -20
Input
4
1 1
1 2
1 3
1 4
2 5
2 5
2 5
2 5
Output
0 2 5
Input
5
-1 1
-1 1
-1 1
-1 1
-1 4
-1 1
-1 1
-1 1
-1 4
-1 4
Output
-1
Note

In the last example, if $$$S=1,X=0,Y=0$$$, then coordinate $$$(-1,4)$$$ will have 1 drop of disinfection substances while having 2 types of bacteria.