농구 골대 세우기

격자 나라에는 정수 좌표마다 마을이 있다. 어떤 두 마을 사이의 거리는 길을 따라 이동하는 최단거리, 즉 맨해튼 거리로 계산한다. 좌표 (x1, y1)에서 (x2, y2)까지의 거리는 |x2 - x1| + |y2 - y1|이다.

농구를 좋아하는 마을 n개의 위치와 각 마을의 사람 수가 주어진다. 나라에서는 모든 농구를 좋아하는 마을을 위해 농구 골대를 하나 세우려고 한다.

골대는 정수 좌표의 한 마을에 세워야 하며, 그 마을이 입력으로 주어진 마을일 필요는 없다. 각 농구를 좋아하는 마을에 대해 (그 마을에서 골대까지의 거리) × (그 마을의 사람 수)를 계산했을 때, 그 합이 최소가 되는 골대의 위치를 구하라.

첫 줄에 농구를 좋아하는 마을의 개수 n이 주어진다. 다음 n개의 줄에는 한 마을의 정보 xi yi pi가 주어진다. 이는 마을의 좌표가 (xi, yi)이고, 그 마을에서 농구를 좋아하는 사람 수가 pi명이라는 뜻이다.

두 마을의 위치가 같은 경우는 없다.

골대를 세울 마을의 좌표 x y를 한 줄에 출력한다. 답이 여러 개라면 x좌표가 가장 작은 위치를 고르고, 그래도 여러 개라면 y좌표가 가장 작은 위치를 고른다.

• 1 ≤ n ≤ 100,000
• -1,000,000 ≤ xi, yi ≤ 1,000,000
• 1 ≤ pi ≤ 1,000