Processing math: 100%
Convex hull - MarisaOJ: Marisa Online Judge

Convex hull

Time limit: 1000 ms
Memory limit: 256 MB

Determine the convex hull of $n$ points.

Input

  • The first lines contains an integer $n$.
  • The next $n$ lines, each line contains a point $(x, y)$.

Output

  • Print $p$, the number of points in the convex hull on one line.
  • The next $p$ lines, print the points in the convex hull in any order.

Constraints

  • $ 1 \le n \le 10^5$.
  • $-10^9 \le x, y \le 10^9$.

Example

Input:

8
7 1
16 2
1 5
13 8
11 9
5 10
2 8
7 5

Output:

7
7 1
16 2
13 8
11 9
5 10
2 8
1 5