Description

Given $n$ and $a, b$, find a linear function $f(x) = k(x - x_0) + y_0 \ (1 \le k \le 10^{12})$ such that $f(x)$ divides the $n$ points in the plane into two parts whose counts are in the ratio $a : b$.

If you do not know why a linear function is written in this form, here is the definition of point-slope form.

Input Format

The first line contains three integers $n, a, b$, representing the number of points and the ratio you want to split into.

The next $n$ lines each contain two integers $x_i, y_i$, representing the point $(x_i, y_i)$ on the plane.

The testdata guarantees that no two points coincide.

Output Format

Output one line with three integers, representing $k, x_0, y_0$ in the statement.

You must ensure that $1 \le k \le 10^{12}, -10^5 \le x_0, y_0 \le 10^{5}$.

If a point lies exactly on the line you give, we consider it to be above the line.

2 1 1
0 1
1 0

1 0 0

Hint

This problem uses bundled tests.

$\text{Subtask 1 (10 pts)}:$ guaranteed $n \in \{2, 3\}$.

$\text{Subtask 2 (30 pts)}:$ guaranteed $\left|x_i\right|, \left|y_i\right| \le 10$.

$\text{Subtask 3 (60 pts)}:$ guaranteed $2 \le n \le 10^5$, $0 \le \left|x_i\right|, \left|y_i\right| \le 10^5$.

For all testdata, it is guaranteed that $(a + b) | n$ and $ab \neq 0$.

Special Judge

This problem uses $\text{Special Judge}$.

List of spj return messages:

Your answer is correct!: your result is correct.

Your answer is wrong, expected ratio as a : b, found A : B.: your function is incorrect; it splits all points into two parts with ratio $A : B$ instead of $a : b$.

Oops, data out of range!: the coordinates or slope you provided are outside the required range.

Note that during the contest, you cannot see the return message from Special Judge.

Translated by ChatGPT 5