Convex hull

Given n points on a plane, your task is to construct their convex hull. It is guaranteed that the convex hull is not degenerate.

Input

The first line contains the integer n (3 ≤ n ≤ 10^5), representing the number of points. Each of the following n lines contains two integers x[i] and y[i] (-10^9 ≤ x[i], y[i] ≤ 10^9), which are the coordinates of the points.

Please note: The points are arbitrary and may include duplicates. Additionally, a large number of points may lie on the same line.

Output

On the first line, output the number of vertices n of the convex hull. The subsequent n lines should list the coordinates of the vertices in the order they are traversed. Ensure that no three consecutive points are collinear.

Examples