Magic Swords

Time limit2sMemory limit512 MB

Summary

Given n ages, build a forest where each node has at most two children and every child is at least k years younger than its parent, or report that none exists.

Level: Medium7 of 10
Topics: Greedy, Sorting, Tree, Implementation
Solved: No attempts yet

Problem

The archaeology department of NIICHAVO decided to study the ancient Flatland magic swords. After examining every available specimen, they found that almost all the swords are in fact copies of one another.

Specifically, the first magic sword was made in the distant past. After that, from time to time, craftsmen would take one of the existing magic swords and make a copy of it. Naturally, the copy differed from the original, but overall it inherited some of the original's traits.

Since making a copy of a magic sword reduces its magical power, the scientists established that at most two copies were made from each sword. They also established that a copy could be made no earlier than $k$ years after the original was made.

The scientists have $n$ swords, and they know the age of each one. They want to find out which sword was made first, and for every other sword, from which sword it was copied. Unfortunately, the age information may not be enough to reconstruct this uniquely, but the scientists will accept any valid option.

Input

The first line of the input contains two numbers $n$ and $k$ : the number of swords the scientists have, and the minimum age required for a copy to be made from a sword ( $1 \le n \le 100\,000$ , $1 \le k \le 10^8$ ). The next line contains $n$ numbers $a_1, a_2, \ldots, a_n$ , where $a_i$ ( $0 \le a_i \le 10^{9}$ ) is the age of the $i$ -th sword.

Output

For each sword, print the number of the sword it was copied from. Note that at most two copies could be made from each sword.

If a sword is the first one made, print 0 for that sword.

If there are several possible solutions, print any of them.

If the scientists are wrong and the required sequence of sword copies does not exist, print the single number $-1$ .

Examples2

Example 1
Input
```
6 3
2 10 6 0 5 2
```
Expected output
```
5 0 2 3 2 5
```
Example 2
Input
```
4 3
10 1 1 1
```
Expected output
```
-1
```