== include(page="template/taskheader" task_id="partitie") ==

Poveste si cerinta...

Fie o multime finita $M$. Se numeste partitie a multimii $M$ un set de submultimi {$S{~1~}$}, {$S{~2~}$}... {$S{~K~}$} cu proprietatile:
 
* reuniunea celor $K$ submultimi are ca rezultat multimea $M$
* intersectia oricaror doua submultimi distincte este multimea vida
 
Dandu-se multimea $M$ cu $N$ elemente, sa se determine numarul minim de submultimi in care poate fi partitionata astfel incat pentru orice submultime {$S{~i~}$} de cardinal cel putin $2$, diferenta (in modul) dintre oricare $2$ elemente este mai mare sau egala cu $D$.

h2. Date de intrare

Fisierul de intrare $partitie.in$ ...

Fisierul de intrare $partitie.in$ contine pe prima linie numarele naturale $N$ si $D$, cu semnificatia din enunt. Fiecare din urmatoarele $N$ linii contine cate un numar, indicand un element al multimii $M$.

h2. Date de iesire

In fisierul de iesire $partitie.out$ ...

In fisierul de iesire $partitie.out$ se va afisa pe prima linie numarul minim de submultimi dintr-o partitie care indeplineste conditia impusa. Urmatoarele N linii......???? Daca sunt mai multe solutii posibile se va afisa oricare.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 300 000$
* $D$ si elementele multimii $M$ sunt numere naturale intregi din intervalul $[-10^9^, 10^9^]$

h2. Exemplu
table(example). |_. partitie.in |_. partitie.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|5 3
9
2
11
5
3
|2
1
1
2
1
2|

h3. Explicatie