tunel

문제

A tunnel is drawn in the rectangular coordinate system. 

The ceiling of the tunnel starts in (0,1) and ends in (N,1). 

The floor of the tunnel starts in (0,-1) and ends in (N,-1). 

The path through the tunnel starts in (0,0) and ends in (N,0). 

The ceiling, floor and path are sequences of horizontal and vertical segments such that each corner has integer coordinates, and the x-coordinate of each corner is greater than or equal to the x-coordinate of the previous corner. 

All of the y-coordinates of the ceiling and the floor will be integers between -1000 and 1000, inclusive. 

The path must not touch the ceiling or the floor of the tunnel, even on corners. 

The tunnel from the third example is given in the figure below. The ceiling and the floor are represented with solid lines and the path is represented with the dashed line. 

[이미지 1]

Write a program that finds some shortest path through the tunnel. 

입력

The first line of input contains an integer N, 1 ≤ N ≤ 100,000, the width of the tunnel. 

The second line contains N integers – y-coordinates of the horizontal segments of the ceiling, from left to right. 

The third line contains N integers – y-coordinates of the horizontal segments of the floor, from left to right. 

출력

The first and only line of output should contain N integers – y-coordinates of the horizontal segments of the path, from left to right. 

Note: the test data will be such that a solution, although not necessarily unique, always exists.