Traffic Light Timings

In a city, there is a straight road with N intersections. Each intersection is equipped with a traffic light. The distance between intersection i and intersection i+1 is given as $A_i$ kilometers for $1\le i < N$. For each intersection, the red light lasts for $R_i$ minutes and the green light lasts for $G_i$ minutes, with no yellow light. At time 0, all traffic lights switch from red to green simultaneously.

A car starts at a point that is M kilometers away from intersection 1, and it moves at a constant speed of 1 kilometer per minute. The car must obey the traffic signals; that is, it may not cross an intersection during a red light. When it reaches an intersection, if the traffic light is green, it passes immediately; if it is red (or turns red exactly at the moment of arrival), the car waits until the light turns green.

Compute the time at which the car passes each intersection. For each intersection, simulate the following:

• The car starts with an initial time $t = M$ (the time taken to travel from its starting position to intersection 1).
• For the current intersection with parameters $R_i$ and $G_i$, let the cycle period be $T_i = R_i + G_i$. If $t \mod T_i \ge G_i$, the light is red on arrival and the car must wait until the next green phase; that is, it waits for $T_i - (t \mod T_i)$ minutes.
• After passing the intersection, if there is a next intersection, add the travel time $A_i$ to $t$ to simulate the journey to the next intersection.

Output the passing time for each intersection.

inputFormat

The input consists of 4 lines:

• The first line contains two integers N and M ($1 \le N \le 10^5$, $0 \le M \le 10^9$) -- the number of intersections and the initial distance (in kilometers) from intersection 1.
• The second line contains N-1 integers: $A_1, A_2, \ldots, A_{N-1}$, where $A_i$ is the distance (in kilometers) between intersection i and i+1.
• The third line contains N integers: $R_1, R_2, \ldots, R_N$, where $R_i$ is the duration (in minutes) of the red light at intersection i.
• The fourth line contains N integers: $G_1, G_2, \ldots, G_N$, where $G_i$ is the duration (in minutes) of the green light at intersection i.

outputFormat

Output N integers separated by spaces, where the i-th integer represents the time (in minutes) at which the car passes intersection i.

sample

2 3
5
3 4
5 2

3 12