Art Gallery

The K gallery is known for its unusual structure with many walls. Two lamps stand at the two end corners of one wall to light the inside, and these two lamps leave no dark spot in the building. Every point inside the building receives light from at least one lamp.

Hong Gildong, who is preparing for the informatics olympiad, likes this building and comes to visit whenever he has time. During one visit he wondered what the shortest path joining two points inside the gallery looks like. Remembering the trouble he had implementing a shortest path algorithm for a general polygon, he thought that this unusual structure, lit everywhere by two lamps, might make the shortest path easy to find.

The gallery is a polygon $P = (v_0, v_1, \ldots, v_{n-1})$ with $n$ vertices. The list of vertices is the sequence met while walking counterclockwise along the boundary of the polygon. The lamps sit at the vertices $v_0$ and $v_1$. The edge $(v_0, v_1)$ is a horizontal segment, and the $x$ coordinate of $v_0$ is always smaller than the $x$ coordinate of $v_1$. Every vertex other than $v_0$ and $v_1$ has a $y$ coordinate larger than the $y$ coordinate of $v_0$.

A point $q$ inside the gallery receives light from a lamp $v$ when the segment joining the two points $q$ and $v$ does not meet the outside of $P$. Note that every point of $P$ receives light from $v_0$ or from $v_1$.

Figure 1. Every point of the polygon receives light from $v_0$ or from $v_1$.

In the polygon of Figure 1 the vertices $v_8$ and $v_{11}$ receive light only from $v_1$, and the vertices $v_3$ and $v_4$ receive light only from $v_0$. The remaining vertices receive light from both lamps. It is well known that a shortest path between two vertices bends only at vertices of the polygon. For example, the shortest path between the two vertices $v_4$ and $v_{11}$ is $(v_4, v_5, v_9, v_{11})$, and the shortest path between the two vertices $v_5$ and $v_1$ is the single segment $(v_5, v_1)$.

Help Hong Gildong: given two vertices of the polygon $P$, write a program that finds the shortest path between the two vertices. The length of a path is the sum of the Euclidean lengths of the segments that form it.

The first line contains an integer $n$, the number of vertices of the polygon $P$ ($3 \le n \le 100000$). Each of the next $n$ lines contains two integers, the coordinates of a vertex $v_i$ of $P$, starting from $v_0$ ($i = 0, 1, \ldots, n-1$). Each coordinate is between $-10^9$ and $10^9$.

Every point of $P$ receives light from $v_0$ or from $v_1$. The vertices $v_0$ and $v_1$ have the same $y$ coordinate, and $v_0$ has a smaller $x$ coordinate than $v_1$. Every vertex other than $v_0$ and $v_1$ has a larger $y$ coordinate than $v_0$. No three consecutive vertices along the boundary of $P$ lie on one straight line.

The last line contains two integers $i$ and $j$, the numbers of the two vertices $v_i$ and $v_j$ whose shortest path is asked for ($i \ne j$). The vertex $v_i$ is the start and the vertex $v_j$ is the goal.

Let $(w_0, w_1, \ldots, w_{m-1})$ be the shortest path joining the two given vertices $v_i$ and $v_j$, where $w_0 = v_i$, $w_{m-1} = v_j$, and $w_k$ ($1 \le k \le m-2$) is a point where the shortest path bends. Print $m$ on the first line, and on the second line print the numbers of the vertices of $P$ that correspond to $w_k$, in order ($0 \le k \le m-1$). If the shortest path passes through a vertex without bending there, do not print the number of that vertex.