There are n seats in the train's car and there is exactly one passenger occupying every seat. The seats are numbered from 1 to n from left to right. The trip is long, so each passenger will become hungry at some moment of time and will go to take boiled water for his noodles. The person at seat i (1 ≤ i ≤ n) will decide to go for boiled water at minute t_i.

Tank with a boiled water is located to the left of the 1-st seat. In case too many passengers will go for boiled water simultaneously, they will form a queue, since there can be only one passenger using the tank at each particular moment of time. Each passenger uses the tank for exactly p minutes. We assume that the time it takes passengers to go from their seat to the tank is negligibly small. 

Nobody likes to stand in a queue. So when the passenger occupying the i-th seat wants to go for a boiled water, he will first take a look on all seats from 1 to i - 1. In case at least one of those seats is empty, he assumes that those people are standing in a queue right now, so he would be better seating for the time being. However, at the very first moment he observes that all seats with numbers smaller than i are busy, he will go to the tank.

There is an unspoken rule, that in case at some moment several people can go to the tank, than only the leftmost of them (that is, seating on the seat with smallest number) will go to the tank, while all others will wait for the next moment.

Your goal is to find for each passenger, when he will receive the boiled water for his noodles.

Input

The first line contains integers n and p (1 ≤ n ≤ 100 000, 1 ≤ p ≤ 10^9) — the number of people and the amount of time one person uses the tank.

The second line contains n integers t_1, t_2, ..., t_n (0 ≤ t_i ≤ 10^9) — the moments when the corresponding passenger will go for the boiled water.

Output

Print n integers, where i-th of them is the time moment the passenger on i-th seat will receive his boiled water.

Example

Input


5 314
0 310 942 628 0


Output


314 628 1256 942 1570 

Note

Consider the example.

At the 0-th minute there were two passengers willing to go for a water, passenger 1 and 5, so the first passenger has gone first, and returned at the 314-th minute. At this moment the passenger 2 was already willing to go for the water, so the passenger 2 has gone next, and so on. In the end, 5-th passenger was last to receive the boiled water.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.PriorityQueue;
import java.util.Collection;
import java.util.AbstractQueue;
import java.io.IOException;
import java.util.Deque;
import java.io.UncheckedIOException;
import java.util.AbstractCollection;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author daltao
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "daltao", 1 << 27);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            TaskC solver = new TaskC();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class TaskC {
        public void solve(int testNumber, FastInput in, FastOutput out) {
            int n = in.readInt();
            long p = in.readInt();

            PriorityQueue<Event> events = new PriorityQueue<>(2 * n, (a, b) -> Long.compare(a.time, b.time));

            Seat[] seats = new Seat[n];
            for (int i = 0; i < n; i++) {
                seats[i] = new Seat();
                seats[i].id = i;
                Event e = new Event();
                e.type = 2;
                e.which = seats[i];
                e.time = in.readInt();
                events.add(e);
            }
            MinQueue<Seat> inQue = new MinQueue<>(n, (a, b) -> a.id - b.id);
            PriorityQueue<Seat> wait = new PriorityQueue<>(n, (a, b) -> a.id - b.id);

            boolean state = false;
            while (!events.isEmpty()) {
                long time = events.peek().time;
                while (!events.isEmpty() && events.peek().time == time) {
                    Event head = events.remove();
                    if (head.type == 2) {
                        wait.add(head.which);
                    } else if (head.type == 1) {
                        state = false;
                        inQue.deque();
                        head.which.ans = head.time;
                    }
                }

                while (!wait.isEmpty() && (inQue.isEmpty() || inQue.query().id > wait.peek().id)) {
                    Seat s = wait.remove();
                    inQue.enqueue(s);
                }

                if (!state && !inQue.isEmpty()) {
                    state = true;
                    Seat s = inQue.peek();
                    Event e = new Event();
                    e.which = s;
                    e.type = 1;
                    e.time = time + p;
                    events.add(e);
                }
            }

            for (Seat s : seats) {
                out.append(s.ans).append(' ');
            }
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static class Event {
        int type;
        Seat which;
        long time;

    }

    static class Seat {
        int id;
        long ans;

        public String toString() {
            return "" + id;
        }

    }

    static class MinQueue<T> {
        Deque<T> data;
        Deque<T> increasing;
        Comparator<T> comparator;

        public boolean isEmpty() {
            return data.isEmpty();
        }

        public MinQueue(int cap, Comparator<T> comparator) {
            data = new ArrayDeque<>(cap);
            increasing = new ArrayDeque<>(cap);
            this.comparator = comparator;
        }

        public void enqueue(T x) {
            while (!increasing.isEmpty() && comparator.compare(x, increasing.peekLast()) < 0) {
                increasing.removeLast();
            }
            increasing.addLast(x);
            data.addLast(x);
        }

        public T deque() {
            T head = data.removeFirst();
            if (increasing.peekFirst() == head) {
                increasing.removeFirst();
            }
            return head;
        }

        public T query() {
            return increasing.peekFirst();
        }

        public T peek() {
            return data.peekFirst();
        }

    }

    static class FastOutput implements AutoCloseable, Closeable {
        private StringBuilder cache = new StringBuilder(1 << 20);
        private final Writer os;

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

    }
}

