D. Desired Distance
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n - 1$$$ points $$$P_i = (x_i, y_i)$$$ on a 2D plane, some of which may coincide. Let the distance between two points $$$P_i$$$ and $$$P_j$$$ be defined as follows:

$$$$$$d(i, j) = \max(|x_i - x_j|, |y_i - y_j|).$$$$$$

Add a new point $$$(x_n, y_n)$$$ with integer coordinates in such a way that the median of the multiset $$$\{d(i, j)~|~1 \le i \lt j \le n\}$$$ will equal a given value $$$k$$$, or state that it is impossible to do so. The added point is allowed to coincide with previously existing points.

Recall that for a multiset containing an odd number $$$q$$$ of elements, its median can be obtained as follows: write down all the elements of the multiset in the sorted order, then take the $$$\left(\frac{q + 1}{2}\right)$$$-th element from that order.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \lt 2 \cdot 10^5$$$): the number of points after your addition. It is guaranteed that $$$\frac{n(n-1)}{2}$$$ is odd.

The second line contains an integer $$$k$$$ ($$$1 \le k \le 5 \cdot 10^5$$$): the desired median distance.

The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 5 \cdot 10^5$$$): the coordinates of the $$$i$$$-th previously existing point.

Output

If it is possible to add a point with integer coordinates $$$(x_n, y_n)$$$, such that $$$0 \le x_n, y_n \le 10^6$$$ and the median of the multiset of all distances becomes equal to $$$k$$$, print the coordinates of any such point.

Otherwise, print a single integer $$$-1$$$.

Examples
Input
3
4
0 3
7 0
Output
4 3
Input
6
100
0 10000
10000 0
10000 10000
0 0
5000 5000
Output
-1