터널

직교좌표 평면 위에 터널이 있다.

터널의 천장은 (0, 1)에서 시작해 (N, 1)에서 끝난다. 터널의 바닥은 (0, -1)에서 시작해 (N, -1)에서 끝난다. 터널을 지나는 경로는 (0, 0)에서 시작해 (N, 0)에서 끝나야 한다.

천장, 바닥, 경로는 모두 x축 또는 y축에 평행한 선분들을 이어 붙인 형태이다. 모든 꼭짓점은 정수 좌표이고, 선분을 따라 진행할 때 다음 선분의 x좌표는 이전 선분의 x좌표보다 작아지지 않는다.

천장과 바닥의 y좌표는 각각 -1000 이상 1000 이하의 정수이다.

경로는 천장이나 바닥에 닿아서는 안 된다. 꼭짓점에서도 천장이나 바닥에 닿으면 안 된다.

그림은 하나의 터널 구성을 보여 준다. 천장과 바닥은 실선으로, 경로는 점선으로 표시되어 있다.

터널을 통과하는 최단 경로를 구하는 프로그램을 작성하시오.

첫째 줄에 터널의 너비 N(1 <= N <= 100,000)이 주어진다.

둘째 줄에는 천장의 y좌표 N개가 왼쪽부터 오른쪽 순서로 주어진다.

셋째 줄에는 바닥의 y좌표 N개가 왼쪽부터 오른쪽 순서로 주어진다.

첫째 줄에 경로의 y좌표 N개를 왼쪽부터 오른쪽 순서로 출력한다.

최단 경로가 여러 개일 수 있지만, 조건을 만족하는 최단 경로는 항상 존재한다.