CSES - Aalto Competitive Programming 2024 - wk5 - Wed - Manhattan sightseeing
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Uolevi has organized a group vacation to New York. Now people have scattered all over Manhattan and Uolevi is choosing a place to regroup. Manhattan's infrastructure is grid-like: there are vertical and horizontal streets. Uolevi's group has n people numbered 1,2,\dots,n and the i-th person is now at the intersection of roads x_i and y_i. Help Uolevi pick the intersection that minimizes the maximum distance to a person from the group.

Formally, the distance between intersections (a, b) and (c, d) is |a-c| + |b-d|.

Input

The first line contains a single integer n. The i-th of next n following lines contains two integers x_i and y_i.

Output

Print the coordinates of an intersection that minimizes the maximum distance. If there are multiple answers, print any.

Constraints

  • 1 \leq n \leq 10^5
  • 1 \leq x_i, y_i \leq 10^9

Example 1

Input:

4
0 0
2 0
0 2
2 2

Output:

1 1

Example 2

Input:

5
5 1
7 8
3 2
5 6
9 4

Output:

6 4

Example 3

Input:

10
8 1
9 3
8 4
5 8
3 4
1 6
4 7
4 4
5 8
1000000000 1000000000

Output:

500000002 500000001