Score : $450$ points

Problem Statement

There are $N$ points on a two-dimensional plane. $N$ is odd. The $i$-th point is at $(x\_i, y\_i)$. All point coordinates are distinct.

Determine whether there exists a line passing through more than half of the $N$ points, and if so, output it.

For any input satisfying the constraints, if a line satisfying the condition exists, it can be expressed as $ax+by+c=0$ using integers $a,b,c$ with $-10^{18} \leq a,b,c \leq 10^{18}$ (where $(a,b,c) \neq (0,0,0)$). Output these $a,b,c$.

Constraints

• $3 \leq N \leq 5 \times 10^5$
• $N$ is odd.
• $-10^8 \leq x\_i \leq 10^8$
• $-10^8 \leq y\_i \leq 10^8$
• If $i \neq j$, then $(x\_i, y\_i) \neq (x\_j, y\_j)$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

Output

If no line satisfying the condition exists, output No.

If a line satisfying the condition exists, output two lines. On the first line, output Yes, and on the second line, output $a,b,c$ in this order separated by spaces. $a,b,c$ must satisfy $-10^{18} \leq a,b,c \leq 10^{18}$ and $(a,b,c) \neq (0,0,0)$.

If there are multiple solutions, any of them will be considered correct.

The line $2x+y-8=0$ passes through the $2$nd and $3$rd points, so it satisfies the condition.

No line satisfying the condition exists.

Samples

3
1 1
3 2
2 4

Yes
2 1 -8

5
5 2
1 3
2 6
4 4
5 4

No

11
-9374372 85232388
-60705467 86198234
-7475320 80628487
98066347 -23868213
-12177678 85284287
30535572 -35358356
51324557 22410787
28854279 44658587
-28804873 82911971
65052073 8819187
-67744430 68365758

Yes
4655800 4702358 -344340416016346