Distant Stars

The night sky seen from the planet KOI, in an imaginary universe, holds many bright stars. Jeongbo Na, a high school student who lives there, photographs the sky with a fixed camera every night at midnight. The stars in each photo always land on integer coordinates of a two dimensional plane.

Comparing the photos day by day shows that some stars stay at the same coordinates while others move at a constant velocity. A velocity is written $[dx, dy]$, where $dx$ is the change of the x coordinate over one day and $dy$ is the change of the y coordinate over one day. Both are integers. The velocity of each star is independent of the others, and two stars can share the same coordinates at any time. They never actually collide. A star that does not move has velocity $[0, 0]$.

For example, the photo below is the first one Jeongbo Na took, on day 0. Star A is at $(0, 0)$, star B is at $(5, 0)$, and star C is at $(3, -3)$.

The next photo, taken one day later on day 1, shows the three stars at $(2, 0)$, $(4, 0)$, and $(4, -2)$.

So star A has velocity $[2, 0]$, star B has velocity $[-1, 0]$, and star C has velocity $[1, 1]$. In the photo of day 2 the three stars are therefore at $(4, 0)$, $(3, 0)$, and $(5, -1)$.

Jeongbo Na records the distance between the two farthest stars in every photo. Two stars whose x coordinates differ by $p$ and whose y coordinates differ by $q$ are at distance $\sqrt{p^2+q^2}$. In the photo of day 0 the farthest pair is A and B at distance $5$, and in the photo of day 1 it is A and C at distance $\sqrt{8}$.

Given the initial coordinates and velocities of the stars and the last photo day, write a program that finds the photo day on which the distance between the two farthest stars is smallest, together with the square of that distance on that day. If several photo days give that smallest distance, find the earliest one.

In the example above with last photo day 3, the largest distance is $5$ on day 0, $\sqrt{8}$ on day 1, $\sqrt{5}$ on day 2, and $4$ on day 3. The smallest of these is $\sqrt{5}$, so the answer is day 2 and the squared value $5$.

The first line has the number of stars $N$ ($2 \le N \le 30000$) and the last photo day $T$ ($0 \le T \le 10^7$). Each of the next $N$ lines has four integers: the coordinates $x$, $y$ of one star and its velocity $dx$, $dy$. The values satisfy $|x| \le 10^7$, $|y| \le 10^7$, $|dx| \le 100$, and $|dy| \le 100$. Several stars may start at the same coordinates.

On the first line, print the photo day on which the distance between the two farthest stars is smallest. If several photo days give that smallest distance, print the earliest one. On the second line, print the square of that distance on that day as an integer.