먼 별

가상의 우주에 있는 KOI 별에서 바라본 밤하늘에는 밝게 빛나는 별이 많다. 이 별에 사는 고등학생 나정보는 고정한 카메라로 매일 밤 자정에 하늘을 찍는다. 사진에 찍힌 별의 위치는 언제나 2차원 평면의 정수 좌표로 표현된다.

날마다 찍은 사진을 비교해 보니 어떤 별은 늘 같은 좌표에 있고, 어떤 별은 일정한 속도로 움직인다. 별의 속도는 $[dx, dy]$로 적는다. $dx$는 하루 동안의 x좌표 변화량, $dy$는 하루 동안의 y좌표 변화량이며 둘 다 정수다. 각 별의 속도는 다른 별과 무관하고, 별끼리 언제든 같은 좌표에 놓일 수 있다. 다만 실제로 충돌하지는 않는다. 움직이지 않는 별의 속도는 $[0, 0]$이다.

예를 들어 아래 사진은 나정보가 처음 찍은 사진, 즉 촬영일 0의 사진이다. 별 A는 $(0, 0)$, 별 B는 $(5, 0)$, 별 C는 $(3, -3)$에 있다.

다음 사진은 하루 뒤인 촬영일 1의 사진으로, 세 별의 좌표가 $(2, 0)$, $(4, 0)$, $(4, -2)$로 바뀌었다.

즉 별 A의 속도는 $[2, 0]$, 별 B의 속도는 $[-1, 0]$, 별 C의 속도는 $[1, 1]$이다. 따라서 촬영일 2의 사진에서 세 별의 좌표는 $(4, 0)$, $(3, 0)$, $(5, -1)$이 된다.

나정보는 사진마다 가장 멀리 떨어진 두 별의 거리를 기록한다. x좌표 차이가 $p$이고 y좌표 차이가 $q$인 두 별의 거리는 $\sqrt{p^2+q^2}$로 정의한다. 촬영일 0의 사진에서 가장 멀리 떨어진 두 별은 A와 B이고 거리는 $5$, 촬영일 1의 사진에서는 A와 C이고 거리는 $\sqrt{8}$이다.

별들의 초기 좌표와 속도, 마지막 촬영일이 주어졌을 때 가장 멀리 떨어진 두 별의 거리가 최소인 촬영일과 그날 그 거리의 제곱을 구하는 프로그램을 작성하시오. 그런 촬영일이 여럿이면 그중 가장 이른 촬영일을 구한다.

앞의 예에서 마지막 촬영일이 3이라면 각 촬영일의 최대 거리는 $5$(촬영일 0), $\sqrt{8}$(촬영일 1), $\sqrt{5}$(촬영일 2), $4$(촬영일 3)이다. 이 중 $\sqrt{5}$가 가장 작으므로 답은 촬영일 2와 제곱값 $5$다.

첫 줄에 별의 개수 $N$ ($2 \le N \le 30000$)과 마지막 촬영일 $T$ ($0 \le T \le 10^7$)가 주어진다. 이어지는 $N$개의 줄에는 각 별의 좌표 $x$, $y$와 속도 $dx$, $dy$를 나타내는 정수 네 개가 주어진다. $|x| \le 10^7$, $|y| \le 10^7$, $|dx| \le 100$, $|dy| \le 100$이다. 좌표가 같은 별이 여럿 들어올 수도 있다.

첫 줄에 가장 멀리 떨어진 두 별의 거리가 최소인 촬영일을 출력한다. 그런 촬영일이 여럿이면 가장 이른 촬영일을 출력한다. 둘째 줄에 그날 그 거리의 제곱을 정수로 출력한다.