3. Gas Station
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A gas station has N fuel pumps, all of which are initially free.

Cars arrive at the gas station from time to time and join a single common queue. As soon as a pump becomes available, the first car in the queue moves to it to refuel. Refueling takes T seconds.

After refueling, the car moves aside to free up the pump, and the driver joins a queue for the checkout counter (since the online payment system is down again). There is only one checkout counter. Processing a payment at the counter takes V seconds.

For each car, determine the time at which it leaves the gas station. You may assume that all movements of cars and drivers occur instantaneously.

Input

The first line contains four space-separated integers:

  • F (1 ≤ F ≤ 105) — the number of cars.
  • N (1 ≤ N ≤ 10) — the number of fuel pumps.
  • T (1 ≤ T ≤ 100) — the time required to refuel one car.
  • V (1 ≤ V ≤ 100) — the time required to process a payment at the checkout counter.

Each of the following F lines contains a single integer X (1 ≤ X ≤ 109) — the arrival time of a car. All arrival times are distinct and are given in ascending order.

Output

For each car, output the time at which it leaves the gas station.

Scoring

Subtask 1 (up to 25 points): F ≤ 100, X ≤ 105

Subtask 2 (up to 36 points): F ≤ 1000, X ≤ 109

Subtask 3 (up to 39 points): F ≤ 105, X ≤ 109

The number of points for a single test may vary between subtasks.

Examples
Input
4 2 10 100
1
2
500
510
Output
111
211
610
710
Input
7 2 5 1
1
2
3
4
500
510
520
Output
7
8
12
13
506
516
526
Note

In Python, you can read 4 integers separated by spaces as follows: f, n, t, v = map(int, input().split())