Tunnel

A tunnel is drawn on a Cartesian plane.

The tunnel ceiling starts at (0, 1) and ends at (N, 1). The tunnel floor starts at (0, -1) and ends at (N, -1). A path through the tunnel must start at (0, 0) and end at (N, 0).

The ceiling, floor, and path are all polylines made by joining segments parallel to the x-axis or y-axis. Every corner has integer coordinates, and as the polyline is followed, the x-coordinate of the next segment never becomes smaller than that of the previous segment.

Each y-coordinate of the ceiling and floor is an integer from -1000 to 1000, inclusive.

The path must not touch the ceiling or the floor, not even at a corner.

The figure shows one possible tunnel. The ceiling and floor are drawn with solid lines, and the path is drawn with a dotted line.

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

The first line contains the tunnel width N (1 <= N <= 100,000).

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

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

Print N y-coordinates of the path on the first line, from left to right.

A shortest path may not be unique, but at least one valid shortest path always exists.