Description

The streets of the New Byte City form a rectangular grid — those running east-west are simply called streets, while those running north-south are called avenues. To avoid mistakes, we shall call them h-streets and v-streets, respectively. The v-streets are numbered from $1$ to $500\ 000\ 000$ eastwards. Similarly, the h-streets are numbered from $1$ to $500\ 000\ 000$ northwards. Every v-street crosses every h-street and, conversely, every h-street crosses every v-street. The distance between two consecutive v-streets, as well as between two consecutive h-streets, is exactly one kilometre.

There are $k$ shops in the city, each one of them situated at a crossroads. Byteasar, the merchant, supplies every single one of the $k$ shops, and furthermore he returns to some of them several times a day with fresh supplies. Recently he has decided to have a warehouse built, from which the goods would be delivered. For obvious reasons, it should stand at a crossroads. The lorry loaded with goods can supply only one shop per course — it leaves the warehouse, delivers to the shop, and returns to the warehouse. The lorry always picks the shortest path from the warehouse to the shop, and the shortest one back (possibly the same one). The distance between points $(x_i, y_i)$ and $(x_j, y_j)$ equals $\max \{ |x_i - x_j|, |y_i - y_j| \}$.

Task: Write a program that:

• reads the locations of shops, as well as the numbers of their daily deliveries, from the standard input,
• determines such a warehouse position that the total distance of the lorry’s daily route is minimal,
• writes the result to the standard output.

Given a grid graph with a set of “bad points” at integer coordinates (multiplicity allowed at the same location), find an integer lattice point that minimizes the sum of Chebyshev distances to all the bad points. Find such a lattice point position.

Input Format

The first line of the standard input contains one integer $n$ ($1 \le n \le 100\ 000$), the number of shops in the New Byte City.

The following $n$ lines contain the shops’ descriptions. The $(i+1)$'th line contains three integers $x_i$, $y_i$ and $t_i$ ($1 \le x_i, y_i \le 500\ 000\ 000$, $1 \le t_i \le 1\ 000\ 000$), separated by single spaces. This triple means that the $i$'th shop lies at the crossing of the $x_i$'th v-street and the $y_i$'th h-street, and the lorry delivers goods to this shop $t_i$ times a day.

Output Format

The first and only line of the standard output should contain two integers $x_m$ and $y_m$, separated by a single space, denoting the optimal position of the warehouse as the crossroads of the $x_m$'th v-street and the $y_m$'th h-street. Should there are many optimal solutions, your program may pick one of them arbitrarily.

3
2 2 1
6 2 1
4 6 1

4 4

Hint

Thanks to @oscar for providing the SPJ.

Translated by ChatGPT 5