Dividing Points by a Linear Function

Given n points in the plane and two positive integers a and b (with n = a + b), your task is to find a linear function in point-slope form

\( f(x)= k(x-x_0)+y_0 \)

with the constraint \(1 \le k \le 10^{12}\), such that this function strictly divides the set of points into two groups: exactly a points lying strictly above the graph of f(x) and exactly b points lying strictly below it. A point \((x_i,y_i)\) is considered to be above the line if \(y_i > f(x_i)\) and below if \(y_i < f(x_i)\). It is guaranteed that none of the points lies exactly on the line if you choose your parameters appropriately.

Hint: One way to construct such a function is to choose k = 1 and x_0 = 0, which gives \( f(x)= x+y_0 \). Then the condition \(y_i > x_i+y_0\) can be rewritten as \(y_i - x_i > y_0\). Let \(t_i= y_i - x_i\) for each point. By selecting a proper value of \(y_0\) between the \(b\text{-th}\) smallest value and the \((b+1)\text{-th}\) smallest value of \(t_i\)'s, you can ensure that exactly b points satisfy \(t_i<y_0\) and the remaining a satisfy \(t_i>y_0\).

inputFormat

The first line contains three integers n, a, and b (with n = a + b). Each of the next n lines contains two integers xi and yi representing the coordinates of a point.

outputFormat

Output three numbers x0, y0, and k (separated by spaces), which define the linear function \( f(x)= k(x-x_0)+y_0 \) that divides the points into two parts with exactly a points above and b points below the line.

sample

4 2 2
0 0
1 1
0 2
1 3

0 1 1