31874번 - 땅땅바 나누기 스페셜 저지

문제

2명이서 쌍쌍바를 공평하게 나누는 법을 알고 있는가? 그 방법은 다음과 같다.

• A가 쌍쌍바를 나눈다.
• B가 나누어진 쌍쌍바 중 하나를 골라서 먹는다.
• A는 B가 고르지 않은 나머지 쌍쌍바를 먹는다.

좌표 평면과 각각의 가치가 $v_i$인 보물 $N$개의 위치가 표시된 보물 지도를 동시에 발견한 준성과 성우는 위 방법을 변형하여 공평하게 보물을 나누려고 한다.

• 준성이 좌표 평면에 직선 $ax = by$를 긋는다. $(0 < \max(|a|, |b|) \leq 2 \times 10^9)$
• 성우가 나누어진 두 평면 중 하나를 선택하여 평면에 포함된 보물을 모두 갖는다. 직선 위에 있는 보물도 성우가 갖는다.
• 준성은 성우가 갖지 않은 모든 보물을 갖는다.

성우는 항상 두 평면 중 보물의 가치의 합이 적지 않게 포함되는 평면을 선택한다. 가난한 대학생 준성을 도와 준성이 가질 보물의 가치의 합이 최대가 되도록 하려면 어떻게 직선을 그어야 하는지 알려주도록 하자!

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \leq N \leq 111,222円)$

다음 $N$개의 줄에 걸쳐 $i$번 보물의 정보가 $x_i,円,円y_i,円,円v_i$ 의 형태로 주어진다. $(-10^9 \leq x_i, y_i \leq 10^9 ; 1 \leq v_i \leq 10^9)$

이는 좌표 $(x_i, y_i)$에 가치가 $v_i$인 보물이 있다는 뜻이다. 주어지는 $x_i, y_i, v_i$는 모두 정수다.

출력

첫 번째 줄에 준성이 가질 보물의 가치의 합이 최대가 되도록 하는 정수 $a$와 $b$를 공백을 사이에 두고 출력한다. 가능한 경우가 여러 개라면 그중 아무거나 출력한다.

제한

힌트