Background

Those who do not share the same values cannot work together.

$\text{.cilohocohc}$ likes eating cake, especially chocolate cake.

$\text{LeverImmy}$ gave her a super huge chocolate cake as a birthday present, with many chocolate puddings decorating the cake.

$\text{.cilohocohc}$ definitely cannot finish such a big cake by herself, so she wants $\text{LeverImmy}$ to help her cut the cake into two pieces, such that the ratio of the number of puddings on the two pieces is $a : b$.

The cake can be abstracted as a 2D plane; and the workshop that made the cake is rather careless, so each pudding is very small and can be regarded as an integer lattice point on the 2D plane.

$\text{LeverImmy}$ has excellent knife skills, so he plans to show off. He will only make one cut along the graph of a linear function with slope not less than $1$ and not greater than $10^{12}$.

He wants to test your intelligence: if it were you, how would you cut it?

Problem 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