Visible Vertices

Given a simple polygon with n vertices, a vertex is considered valid if the line segment connecting the origin (0,0) and that vertex intersects the polygon only at that vertex. In other words, if the intersection of the segment and the polygon is exactly the vertex (and not any other point), then the vertex is valid.

You are given the coordinates of the polygon vertices in order (either clockwise or counterclockwise). The vertices are 1-indexed. Your task is to output all valid vertex indices in increasing order, separated by a space.

The mathematical condition can be expressed as follows: For a vertex V_i with coordinates \( (x_i, y_i) \), let \( P = (0,0) \) and \( Q = V_i \). Let \( E = [A, B] \) be any edge of the polygon that is not incident to \( Q \) (i.e. \( Q \ne A \) and \( Q \ne B \)). The vertex \( V_i \) is valid if for every such edge \( E \), \[ \text{Intersection}(\overline{PQ}, E) = \{Q\} \] where \(\{Q\}\) denotes the singleton set containing the vertex \( Q \).

inputFormat

The first line contains an integer \( n \) (\( 3 \leq n \leq 10^5 \)), the number of vertices of the polygon.

The next \( n \) lines each contain two space-separated integers \( x_i \) and \( y_i \) representing the coordinates of the \( i\text{-th} \) vertex.

The vertices are given in order (either clockwise or counterclockwise) and are 1-indexed.

outputFormat

Output all valid vertex indices in increasing order separated by a single space.

sample

4
1 1
2 0
3 1
2 2

1 2 3 4