G. Slicing the Pizza
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are making an infinite pepperoni pizza, which fills the entire $$$x$$$-$$$y$$$ coordinate plane. You think it might be too much to eat at once, so you decide to cut the plane in half by cutting along some line. You don't want too many pieces of pepperoni on one side, so you want the line to cut through at least $$$1/8$$$th of the pepperoni slices. You are guaranteed that at least one such line exists. Can you find it? If there are multiple lines, find any.

For this problem, assume that the pepperoni slices have radius 0, i.e. they are single points on the grid.

Input

The first line of the input contains a single integer $$$n$$$ ($$$8 \leq n \leq 10^5$$$) – the number of slices of pepperoni.

The next $$$n$$$ lines contain the coordinates of each slice of pepperoni. The $$$i$$$th line contains two integers $$$x_i, y_i$$$ ($$$1 \leq x_i, y_i \leq 10^6$$$) – the $$$x$$$ and $$$y$$$ coordinates of the $$$i$$$th slice of pepperoni, respectively.

You are guaranteed that each pair of coordinates is distinct, i.e. $$$(x_i, y_i) \neq (x_j, y_j)$$$ if $$$i \neq j$$$. You are also guaranteed there exists a valid solution.

Output

Print three space-separated real numbers $$$A, B, C$$$, which represent the line in standard form $$$Ax + By = C$$$. Please ensure $$$-10^{12} \leq A, B, C \leq 10^{12}$$$.

Let $$$D_i$$$ be $$$Ax_i + By_i$$$. A point is considered "valid" if the absolute or relative error of $$$D_i$$$ from $$$C$$$ is at most $$$10^{-6}$$$, i.e. $$$\frac{|D_i - C|}{\max(1, |C|)} \leq 10^{-6}$$$. Your answer will be considered correct if at least $$$\lfloor n / 8 \rfloor$$$ of the points are valid.

Example
Input
8
1 1
2 2
3 3
3 2
9 8
5 5
3 8
4 1
Output
-7.000000000000000 -1.000000000000000 -29.000000000000000
Note

For this sample, any line that goes through a single slice works since we only need $$$\left\lfloor \frac{8}{8} \right\rfloor = 1$$$ slices. For larger $$$n$$$, this is not the case!