Problem

There are a number of cities in a row, and there are two bus lines (Red and Blue) that go between them. Both lines visit all cities in order, but one may take longer than the other to travel between any two cities.

Starting on or moving to the Blue line takes a certain amount of extra time (blueCost). There is no extra time required to start on or move to the Red line.

Your task is to determine the minimum time to travel from the first city to each of the cities.

Input

• red[n]: the times to travel on the Red line
• blue[n]: the times to travel on the Blue line
• blueCost: the time penalty to start on or switch to the Blue line

Output

• long int[n]: the minimum cost of visiting each of the cities from city 0