Problem C
Charlie and the magic eggs
Charlie is undertaking eggs-ellent PhD research into a special kind of magic Easter eggs, which is an eggs-tremely serious matter.
Legend has it that originally there was only one such magic egg. It matures after $k$ years and during its mature years can spawn upto two new eggs like itself. The new eggs then repeat the cylce of reproduction. Being magic, all eggs survive, and Charlie managed to find the ages of a collection of $n$ eggs.
Charlie wants to know if it is possible to find out which egg is spawned from which, given that an egg could only be spawned from another if it’s younger by at least $k$ years. The solution may not be unique, but any possible variant will be acceptable.
Input
The first line of the input file contains two numbers $n$ and $k$ — the number of eggs and the age of maturity ($1 \le n \le 100\, 000$, $1 \le k \le 10^8$). The next line contains $n$ integers: $a_1, a_2, \ldots , a_n$, where $a_i$ ($0 \le a_i \le 10^{9}$) is the age of the $i$-th egg.
Output
For each egg, output the number of the egg from which it was spawned. Note that an egg can spawn a maximum of two eggs.
For the first and oldest egg, output $0$.
If there are multiple possible solutions, output any.
If the legend is mistaken and no sequence of egg spawns exists, output $-1$.
Notes
In the first testcase, egg $1$ (age $2$) may be spawned from egg $3$ (age $6$), egg $2$ is the very first egg, etc.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 3 2 10 6 0 5 2 |
3 0 2 5 2 3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 3 10 1 1 1 |
-1 |