Optimal Warehouse Placement

In New Byte City the streets form a rectangular grid. The intersections are determined by h‐streets (running east–west) and v–streets (running north–south). There are several shops (possibly with multiple deliveries at the same intersection) and a lorry delivers goods from a warehouse to these shops. The lorry leaves the warehouse, delivers to a shop and returns on the shortest possible route. The distance between two intersections ((x_i,y_i)) and ((x_j,y_j)) is measured by the Chebyshev distance

[ d((x_i,y_i),(x_j,y_j)) = \max{|x_i-x_j|,;|y_i-y_j|},. ]

Because each shop receives a given number of daily deliveries, the total daily distance is the sum over all shops of twice the Chebyshev distance (warehouse → shop and back) multiplied by the number of deliveries at that shop. Since the multiplying constant 2 is common to all choices, minimizing the sum

[ \sum_{i=1}^n w_i;\max{|x-x_i|,;|y-y_i|}, , ]

is equivalent to minimizing the total cost. Here (w_i) denotes the number of deliveries (or the weight) at shop (i).

A well known transformation shows that

[ \max{|x-x_i|,|y-y_i|} = \frac{1}{2}\Bigl(|(x+y)-(x_i+y_i)| + |(x-y)-(x_i-y_i)|\Bigr),. ]

Thus one may separately minimize the two sums

[ F(P)=\sum_{i=1}^n w_i;|P-(x_i+y_i)|\quad\text{and}\quad F(Q)=\sum_{i=1}^n w_i;|Q-(x_i-y_i)|,, ]

where the optimum is achieved for any (P) in an interval ([P_{low},P_{high}]) (and similarly for (Q) in ([Q_{low},Q_{high}])).

Because our warehouse must be built at an intersection ((x,y)) (with integer coordinates) and since

[ x = \frac{P+Q}{2}, \quad y = \frac{P-Q}{2},, ]

the numbers (P) and (Q) must have the same parity. In case there are several optimal positions (i.e. several pairs ((x,y)) yielding the same total cost), you are required to choose the one with the maximum coordinates (first maximize (x), and if there is a tie, maximize (y)).

Your task is to choose an intersection ((x,y)) as the location of the warehouse such that the summary Chebyshev distance (weighted by the number of deliveries) is minimized, and, among those, the intersection with the maximum coordinates is chosen.

Note on Implementation

It is sufficient to compute the weighted median for the numbers p = x+y and q = x-y. In one‐dimensional absolute deviation minimization, if the total weight is even and the cumulative weight equals exactly one half at a point, then any number in the corresponding interval is optimal. Since we require the solution with maximum coordinates, when such a plateau occurs we choose the maximum optimal value.

inputFormat

The first line contains a single integer n (\(1 \le n \le 10^5\)), the number of shops.

Each of the following n lines contains three integers x, y and w (\(0 \le x,y \le 5 \times 10^8\); \(1 \le w \le 10^5\)), where (x,y) is the coordinate of a shop and w is the number of daily deliveries to that shop. Note that multiple shops (or deliveries) can be located at the same intersection.

outputFormat

Output two integers \(x\) and \(y\) representing the coordinates of the optimal warehouse location.

sample

1
3 4 5

3 4

</p>