Vehicle Entry Times on a Bridge

Consider a one-lane bridge that can support a maximum weight of (w). There are (n) vehicles waiting in line to cross the bridge, and each vehicle has a weight given in the list. Each vehicle takes (t) seconds to cross the bridge. A vehicle may only enter the bridge if its addition does not cause the total weight of vehicles currently on the bridge to exceed (w). Additionally, vehicles must maintain their order of arrival and cannot start before the previous vehicle. Under the optimal strategy, each vehicle enters as early as possible while satisfying the constraint that the (i)-th vehicle enters no earlier than (t_{i-1} + t), where (t_{i-1}) is the entry time of the previous vehicle. Formally, if (t_i) is the entry time of the (i)-th vehicle, then it must hold that [ t_i \geq t_{i-1} + t] with the first vehicle entering at time 0 (i.e. (t_0 = 0)).

Your task is to compute the entry time for each vehicle. It is guaranteed that the input is such that every vehicle can cross the bridge in order.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

The first line contains three integers (n), (w), and (t) separated by spaces, where (n) is the number of vehicles, (w) is the maximum allowed weight on the bridge, and (t) is the time (in seconds) required for a vehicle to cross the bridge.

The second line contains (n) integers separated by spaces, representing the weights of the vehicles in the order they arrive.

outputFormat

Output to standard output (stdout) a sequence of (n) integers separated by a space, where the (i)-th integer (0-indexed) represents the entry time (in seconds) of the (i)-th vehicle.## sample

4 10 3
3 8 5 2

0 3 6 9