Description

On a plane, for two points $(x,y)$ and $(a,b)$, we say that $(x,y)$ dominates $(a,b)$ if $x\ge a$ and $y\ge b$.

Geometrically, this means that $(a,b)$ lies in the unbounded region whose upper-right corner is $(x,y)$.

Given a set of $n$ points, there exist some points that are not dominated by any other point in the set; these points are called maximal points.

Write a program to find all maximal points and output their coordinates in increasing order of the $x$-coordinate.

Input Format

The input consists of two lines. The first line is a positive integer $n$, the number of points. The second line contains $n$ points’ coordinates. All coordinates are integers. No two points in the input share the same coordinates.

Output Format

Output all maximal points in increasing order of the $x$-coordinate.

The output format is: $(x1,y1),(x2,y2),\cdots,(xk,yk)$.

Note: Each point is separated by ,, and there is no , after the last point. Missing or extra output will be judged incorrect.

5 
1 2 2 2 3 1 2 3 1 4

(1,4),(2,3),(3,1)

Hint

For $50\%$ of the testdata: $1\le n\le 100$; $0\le x,y\le 10^5$.

For $100\%$ of the testdata: $1\le n\le 5\times 10^5$; $0\le x,y\le 10^5$.

Translated by ChatGPT 5