K 미술관은 많은 벽으로 구성된 특이한 구조를 가진 건축물로 유명하다. 미술관의 내부 조명을 위해서 두 개의 전등이 한 쪽 벽의 양 끝 모서리에 설치되어 있는 데, 건물의 내부에 조명이 미치지 않는 곳이 없다. 즉, 건물 내부의 모든 장소는 적어도 하나의 전등으로부터 조명을 받을 수 있다.

정보올림피아드를 준비하는 홍길동은 이 미술관 건물 을 좋아해서 시간이 날 때마다 관람하러 온다. 하루는 미술관을 관람하던 중에 갑자기 “미술관 내부의 두 지 점을 연결하는 최단 경로는 어떤 모양일까?”라는 의문 점이 떠올랐다. 일반적인 다각형에서 최단 경로 알고리즘을 구현하는데 힘들었던 기억을 되살리면서, 두 개의 전등으로 모든 곳을 비출 수 있는 미술관의 특이한 구 조 때문에 최단 경로를 쉽게 구할 수 있지 않을까라는 생각을 하게 되었다.

미술관을 n개의 정점을 가진 다각형 P=(v_0,v_1,...,v_{n-1})로 나타낼 수 있다. 정점 리스트는 다각형 의 경계선을 반시계방향으로 따라가면서 정점들을 순 서대로 나열한 것이다. 미술관에서 전등이 설치된 장소 를 정점 v_0과 v_1이라고 하자. 에지 (v_0,v_1)은 수평 선분으로 v_0의 x-좌표는 항상 v_1의 x-좌표보다 작다. v_0과 v_1을 제외한 나머지 모든 정점의 y-좌표는 v_0의 y-좌표보다 크다(그림 1 참조).

미술관 내부의 어떤 장소 q가 전등 v의 조명을 받는 다는 것은, 두 점 q와 v를 연결하는 선분이 P의 외부와 만나지 않는다는 것을 말한다. P의 모든 점은 v_0 또는 v_1로부터 조명을 받는다는 사실에 유의하라.

그림 1의 다각형에서 정점 v_8과 v_{11}은 v_1로부터만 조명을 받고, v_3과 v_4는 v_0으로부터만 조명을 받는다. 나머지 정점들은 v_0과 v_1 둘 다로부터 조명을 받는다. 두 정점 사이의 최단 경로가 항상 다각형의 정점에서만 꺾인다는 것은 잘 알려져 있다. 예를 들어, 두 정점 v_4와 v_{11} 사이의 최단 경로는 (v_4, v_5, v_9, v_{11})이 다. 두 정점 v_5와 v_1 사이의 최단 경로는 하나의 선 분인 (v_5, v_1)이다.

홍길동을 도와서 다각형 P의 두 정점이 주어질 때, 두 정점 사이의 최단 경로를 구하는 프로그램을 작성 하시오.

첫째 줄에 다각형 P 의 정점의 개수를 나 타내는 정수 n이 주어진다. n은 3 이상100,000 이하이다.

둘째 줄부터 n개의 줄에는 v_0으로부터 시작하여 각 줄마다 하나씩 P 의 각 정점 v_i의 좌표를 나타내는 두 개의 정수가 주어진다(i=0,1,...,n-1). 각 좌표는 -10^9 이상 10^9 이하이다. P 의 모든 점은 v_0 또는 v_1로 부터 조명을 받고, v_0과 v_1의 x-좌표는 같으며, v_0은 v_1보다 x-좌표가 작다. v_0 과 v_1을 제외한 나머지 모든 정점은 v_0 보다 y-좌표가 크다. P 의 경계선을 따라서 연속된 어떤 세 정점도 일직선 상에 위치하지 않는다. 마지막 줄에는 최단 경로를 구하려고 하는 두 정점 v_i와 v_j를 나타내는 정점 번호인 정수 i와 j가 주어진다(i \neq j). 여기서 v_i는 출발점이고 v_j는 도착점이다.

입력으로 주어진 두 정점 v_i와 v_j를 연결하는 최단 경로를 (w_0,w_1,...,w_{m-1})이라고 하자. 여기서 w_0=v_i, w_{m-1}=v_j이고, w_k(1 ≤ k ≤ m-2)는 최단 경로 상의 꺾인 점이다. 첫째 줄에 m을 출력하고, 둘째 줄에 w_k에 해당하는 P의 정점 번호를 순서대로 출력한다(0 ≤ k ≤ m-1).