i cant understanad the problem ,can someone explain it to me

one of the most efficient uses of binary search is to find a range that satisfies a certain condition we want you to do something like that given an array A for each index find the Largest element in the Array A such that that element named x - ai  ≤  v.

where v is a given integer.

Input on the first line you are given two integers n and v where (1  ≤  n  ≤  105) and (0  ≤  v  ≤  109).

then you will be given n integers the array A where (1  ≤  ai  ≤  109).

Output Output n integers where for each i output xi where xi is the largest element in the array where xi - ai  ≤  v.

Examples

input

5 2

5 4 2 1 3

output

5 5 4 3 5