Description

In a city, there is a straight road with $N$ intersections, each equipped with a traffic light. The distance between two adjacent intersections is $A_i$ kilometers $(1 \le i < N)$. At each intersection, the red light lasts $R_i$ minutes and the green light lasts $G_i$ minutes; there is no yellow light. Now, a car starts from a point $M$ kilometers away from intersection $1$, and at that moment, all traffic lights have just switched from red to green. Find the time when this car passes each intersection (the car must not run red lights; its speed is $1$ kilometer per minute).

Input Format

The first line contains two positive integers $N$ and $M$.

The second line contains $N - 1$ positive integers $A_i$.

The third line contains $N$ positive integers $R_i$, the red-light durations (minutes).

The fourth line contains $N$ positive integers $G_i$, the green-light durations (minutes).

Output Format

Output $N$ lines, each containing one positive integer, which is the earliest time when the car passes each intersection.

5 3
2 4 3 2
3 4 3 4 3
2 3 2 3 1

5
7
11
14
16

Hint

For $50\%$ of the testdata, $N \le 1000$.

For $100\%$ of the testdata, $N \le 10^5$, $M, A_i \le 10$, $R_i, G_i \le 5$.

Translated by ChatGPT 5